The Knapsack Problem The Knapsack Problem is a classic in computer science. In i
ID: 3830738 • Letter: T
Question
The Knapsack Problem
The Knapsack Problem is a classic in computer science. In its simplest form it
involves trying to fit items of different weights into a knapsack so that the knapsack
ends up with a specified total weight. You don’t need to fit in all the items.
For example, suppose you want your knapsack to weigh exactly 20 pounds, and you
have five items, with weights of 11, 8, 7, 6, and 5 pounds. For small numbers of
items, humans are pretty good at solving this problem by inspection. So you can
probably figure out that only the 8, 7, and 5 combination of items adds up to 20.
If we want a computer to solve this problem, we’ll need to give it more detailed
instructions. Here’s the algorithm:
1. If at any point in this process the sum of the items you selected adds up to the
target, you’re done.
2. Start by selecting the first item. The remaining items must add up to the
knapsack’s target weight minus the first item; this is a new target weight.
3. Try, one by one, each of the possible combinations of the remaining items.
Notice, however, that you don’t really need to try all the combinations,
because whenever the sum of the items is more than the target weight, you can
stop adding items.
4. If none of the combinations work, discard the first item, and start the whole
process again with the second item.
5. Continue this with the third item and so on until you’ve tried all the
combinations, at which point you know there is no solution.
Some Interesting Recursive Applications 305
In the example just described, start with 11. Now we want the remaining items to
add up to 9 (20 minus 11). Of these, we start with 8, which is too small. Now we
want the remaining items to add up to 1 (9 minus 8). We start with 7, but that’s
bigger than 1, so we try 6 and then 5, which are also too big. We’ve run out of items,
so we know that any combination that includes 8 won’t add up to 9. Next we try 7,
so now we’re looking for a target of 2 (9 minus 7). We continue in the same way, as
summarized here:
Items: 11, 8, 7, 6, 5
==========================================
11 // Target = 20, 11 is too small
11, 8 // Target = 9, 8 is too small
11, 8, 7 // Target = 1, 7 is too big
11, 8, 6 // Target = 1, 6 is too big
11, 8, 5 // Target = 1, 5 is too big. No more items
11, 7 // Target = 9, 7 is too small
11, 7, 6 // Target = 2, 6 is too big
11, 7, 5 // Target = 2, 5 is too big. No more items
11, 6 // Target = 9, 6 is too small
11, 6, 5 // Target = 3, 5 is too big. No more items
11, 5 // Target = 9, 5 is too small. No more items
8, // Target = 20, 8 is too small
8, 7 // Target = 12, 7 is too small
8, 7, 6 // Target = 5, 6 is too big
8, 7, 5 // Target = 5, 5 is just right. Success!
As you may recognize, a recursive routine can pick the first item, and, if the item is
smaller than the target, the routine can call itself with a new target to investigate the
sums of all the remaining items.
Can someone help me put this into code for Java? I cannot for the life of me, figure it out. It needs to be done with 5 randomly generated numbers.
Thanks in advance!
Explanation / Answer
Here is the code in java for the question. Please don't forget to rate the answer if it helped. Thank you very much.
import java.util.ArrayList;
import java.util.Arrays;
public class Knapsack {
/*adds numbers from the numbers list starting from 'start' trying to achieve target. Returns the target that is yet
* to be achieved. If return value is 0, it means the specified target is achieved. Otherwise it could not be achieved
* using hte combiinations.
*/
static int pickToSum(int numbers[], int start, ArrayList<Integer> sack, int target)
{
if(start >= numbers.length )
{//if already all elements are exhausted, return target
return target;
}
for(int i=start;i<numbers.length;i++)
{
System.out.print(" Current Sack = "+Arrays.toString(sack.toArray())+ "Target = "+target+" ");
if(numbers[i] > target)
{
System.out.print(" but "+numbers[i]+ " too big");
continue;
}
//since the number is either less or equal to the target, lets add it to the sack
sack.add(numbers[i]);
if(numbers[i] == target) //the number we added is just same as target, so we don't need further checks
{
System.out.print(" and "+numbers[i] + " is just right. ");
return 0; //return since we already target
}
else
{
//we are yet to reach target... so make another call with a reduced target (target - numbers[i])
//starting from next element i+1
System.out.print(" but "+ numbers[i] + " is too small ");
if(pickToSum(numbers, i+1, sack, target-numbers[i]) == 0 )
return 0;
}
//since the combination starting from this number , remove this number out of sack and try next one in list
sack.remove(sack.size()-1);
}
//if the function did not return from teh previous statements, it means all items are exhausted and
//target is not yet achieved.
System.out.print(", No more items");
return target;
}
public static void main(String[] args) {
int numbers[] = {11,8,7,6,5};
int target = 20;
ArrayList<Integer> sack = new ArrayList<Integer>();
if(pickToSum(numbers, 0, sack, target) == 0)
{
System.out.println(" The following items add up to target of "+target+" "+ Arrays.toString(sack.toArray()));
}
else
{
System.out.println("No combinations of numbers add up to target");
}
}
}
output
Current Sack = []Target = 20 but 11 is too small
Current Sack = [11]Target = 9 but 8 is too small
Current Sack = [11, 8]Target = 1 but 7 too big
Current Sack = [11, 8]Target = 1 but 6 too big
Current Sack = [11, 8]Target = 1 but 5 too big, No more items
Current Sack = [11]Target = 9 but 7 is too small
Current Sack = [11, 7]Target = 2 but 6 too big
Current Sack = [11, 7]Target = 2 but 5 too big, No more items
Current Sack = [11]Target = 9 but 6 is too small
Current Sack = [11, 6]Target = 3 but 5 too big, No more items
Current Sack = [11]Target = 9 but 5 is too small , No more items
Current Sack = []Target = 20 but 8 is too small
Current Sack = [8]Target = 12 but 7 is too small
Current Sack = [8, 7]Target = 5 but 6 too big
Current Sack = [8, 7]Target = 5 and 5 is just right.
The following items add up to target of 20
[8, 7, 5]
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.