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!
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[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];
}