# Help with dynamic programming, knapsack problem

• September 19th, 2010, 07:30 PM
jssutton11
Help with dynamic programming, knapsack problem
Hi, I wrote a code to solve the knapsack 0-1 problem by dynamic programming. At a certain point, around 30 max capacity, the code stops adding new values based on the incrementing max capacity and item values. I have no idea why, it finds the correct solution until the max capacity of the knapsack gets to around 30, and then the answers are screwed up. My code is below. Thanks in advance for the help!

{code}
public Knapsack packDP(int capacity)
{
//initialize 2d array
Knapsack [][] knapsackSolutions = new Knapsack[safe.size() + 1][capacity + 1];

//fill 1st row and 1st columns with empty knapsacks as sentinel values
for (int i = 0; i <= safe.size(); i++)
knapsackSolutions[i][0] = new Knapsack();

for (int j = 0; j <= capacity; j++)
knapsackSolutions[0][j] = new Knapsack();

//each row of the 2d array represents an item. for loop to calculate solutions for each item
for (int itemNum = 1; itemNum <= safe.size(); itemNum++)
{
Item currentItem = safe.get(itemNum - 1);

//get optimal solutions for each weight value in the current item row
for (int weight = 0; weight <= capacity; weight++)
{
if (currentItem.size <= weight)
{
System.out.println("weight = " + weight);
if ( (currentItem.value + knapsackSolutions[itemNum - 1][weight - currentItem.size].value) >
knapsackSolutions[itemNum - 1][weight].value )
{
//create a new knapsack with the new item
knapsackSolutions[itemNum][weight] = new Knapsack(knapsackSolutions[itemNum - 1][weight - currentItem.size], currentItem);
}

else
knapsackSolutions[itemNum][weight] = new Knapsack(knapsackSolutions[itemNum - 1][weight]);

}
else
knapsackSolutions[itemNum][weight] = new Knapsack(knapsackSolutions[itemNum - 1][weight]);

count++;
}

}

//return last item of the 2d array, which is the optimal solution for the capacity
return knapsackSolutions[safe.size()][capacity];
}
{code}
• September 20th, 2010, 06:14 AM
rarryawn
Re: Help with dynamic programming, knapsack problem
Hi, I wasn't able to spot the problem but here is the code indented if its any help to the others!:

Code:

```public Knapsack packDP(int capacity) {   //initialize 2d array   Knapsack [][] knapsackSolutions = new Knapsack[safe.size() + 1][capacity + 1];   //fill 1st row and 1st columns with empty knapsacks as sentinel values   for (int i = 0; i <= safe.size(); i++) {       knapsackSolutions[i][0] = new Knapsack();   }   for (int j = 0; j <= capacity; j++) {       knapsackSolutions[0][j] = new Knapsack();   }   //each row of the 2d array represents an item   //for loop to calculate solutions for each item   for (int itemNum = 1; itemNum <= safe.size(); itemNum++) {       Item currentItem = safe.get(itemNum - 1);       //get optimal solutions for each weight value in the current item row       for (int weight = 0; weight <= capacity; weight++) {         if (currentItem.size <= weight) {             System.out.println("weight = " + weight);                         if (currentItem.value                   + knapsackSolutions[itemNum - 1][weight - currentItem.size].value                   > knapsackSolutions[itemNum - 1][weight].value) {               //create a new knapsack with the new item               knapsackSolutions[itemNum][weight] = new Knapsack(                   knapsackSolutions[itemNum - 1][weight - currentItem.size],                   currentItem);             } else {               knapsackSolutions[itemNum][weight] = new Knapsack(                   knapsackSolutions[itemNum - 1][weight]);             }                     } else {             knapsackSolutions[itemNum][weight] = new Knapsack(               knapsackSolutions[itemNum - 1][weight]);         }         count++;       }   }   //return last item of the 2d array, which is the optimal solution for the capacity   return knapsackSolutions[safe.size()][capacity]; }```