-
September 19th, 2010, 07:30 PM
#1
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
#2
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];
}
Tags for this Thread
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|