Help with dynamic programming, knapsack problem

[jssutton11]

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

[NormR1]

solve the knapsack 0-1 problem

Can you explain this problem?

The code you posted isn't a complete program. If you expect help, can you post a program that compiles and executes and demonstrates the problem.

[jssutton11]

The problem involves a "safe" of 5 items in this case with a weight/size and value. A thief breaks into the safe and has a knapsack of a set capacity which will break if the total weight exceeds the capacity. The goal is to optimize the value/profit of the knapsack by finding the best combination of items that have the most value while keeping within the capacity.

Here is my driver:

public class ThiefDriver
{
	
	public static void main(String[] args) {
	    ///
	    /// Set up experiment:
	    ///
	    int INITIAL = 10 ;
	    int INCREMENT = 10 ;
	    ///
	    /// Create objects with add(NAME,SIZE,VALUE):
	    ///
	    Thief thief = new Thief();
	    thief.add("A",3,4) ;
	    thief.add("B",4,5) ;
	    thief.add("C",7,10) ;
	    thief.add("D",8,11) ;
	    thief.add("E",9,13) ;
	    ///
	    /// Run experiment:
	    ///
	    Thief.Knapsack knapsack;
	    for (int capacity=INITIAL ; capacity <= thief.safe.capacity ; capacity+=INCREMENT) {
	      System.out.println("Capacity = " + capacity) ;
	      thief.count = 0 ;
	      knapsack = thief.packRecursive(capacity) ;
	      System.out.println( "  Recursive value/COUNT: " + knapsack.value + " " + thief.count ) ;
	      thief.count = 0 ;
	      knapsack = thief.packMemoized(capacity) ;
	      System.out.println( "  Memoized value/COUNT: " + knapsack.value + " " + thief.count ) ;
	      thief.count = 0 ;
	      knapsack = thief.packDP(capacity) ;
	      System.out.println( "  DP value/COUNT: " + knapsack.value + " " + thief.count ) ;
	    
	    }
	  }

I've been debugging forever and I can't figure out what is wrong.

[NormR1]

Posting bits and pieces of the program doesn't help much.
Without it all what do you expect?

If you expect help, can you post a program that compiles and executes and demonstrates the problem.

[jssutton11]

Fair enough, here is my full program.

import java.util.*;
import java.math.*;

public class Thief
{
	public Knapsack safe;
	public Knapsack knapsack;
	public static int count;
	
	public Thief()
	{
		//initialize the safe and knapsack
		safe = new Knapsack();
		safe.setCapacity(50);
		knapsack = new Knapsack();
		
	}
	
	public void add(String nm, int sz, int vl)
	{
		safe.addItem(new Item(vl, sz, nm));
	}
	
	public Knapsack packRecursive(int capacity)
	{
		count++;
		//initialize two knapsacks for later comparison
		Knapsack currentKnapsack = new Knapsack();
		Knapsack bestKnapsack = new Knapsack();
		
		for (int i = 0; i < safe.size(); i++)
		{
			if (safe.get(i).size <= capacity)
			{
				//currentKnapsack will find the optimal solution for leftover space recursively
				currentKnapsack = packRecursive(capacity - safe.get(i).size);
				
				if((safe.get(i).value + currentKnapsack.value) > bestKnapsack.value)
				{
					//bestKnapsack will be the current item in the safe + the optimal solution for leftover space
					bestKnapsack = new Knapsack(currentKnapsack, safe.get(i));
				}
			}
		}
		
		return bestKnapsack;
	}
	
	
	public Knapsack packMemoized(int capacity)
	{
		Knapsack [] knapsackMemo = new Knapsack[capacity + 1];
		
		return packMemoized(knapsackMemo, capacity);
	}
	
	private Knapsack packMemoized(Knapsack[] memo, int capacity)
	{
		count++;
		//if we have already calculated the optimal solution for this capacity we can skip the extra work
		if (memo[capacity] != null)
			return memo[capacity];
		
		Knapsack currentKnapsack = new Knapsack();
		Knapsack bestKnapsack = new Knapsack();
		
		for (int i = 0; i < safe.size(); i++)
		{
			if (safe.get(i).size <= capacity)
			{
				currentKnapsack = packMemoized(memo, (capacity - safe.get(i).size));
				
				if((safe.get(i).value + currentKnapsack.value) > bestKnapsack.value)
				{
					bestKnapsack = new Knapsack(currentKnapsack, safe.get(i));
				}
			}
		}
		//save a memo of the calculation to save work later
		memo[capacity] = bestKnapsack;
		
		return bestKnapsack;
	}
	
	
	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);
			System.out.println("**currentItem: s,v " + currentItem.size + " " + currentItem.value);
			//get optimal solutions for each weight value in the current item row
			for (int weight = 1; 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 )
					{
						knapsackSolutions[itemNum][weight] = new Knapsack(knapsackSolutions[itemNum - 1][weight - currentItem.size], currentItem);
						System.out.println("currentItem.value + knapsackSolutions[itemNum - 1][weight - currentItem.size].value = " + (currentItem.value + knapsackSolutions[itemNum - 1][weight - currentItem.size].value));
					}
						
					else
						knapsackSolutions[itemNum][weight] = new Knapsack(knapsackSolutions[itemNum - 1][weight]);
					
					System.out.println("knapsackSolutions[itemNum - 1][weight].value = " + knapsackSolutions[itemNum - 1][weight].value);
				}
				else
					knapsackSolutions[itemNum][weight] = new Knapsack(knapsackSolutions[itemNum - 1][weight]);
				
				
				
				System.out.println("knapsackSolutions[itemNum][weight].value = " + knapsackSolutions[itemNum][weight].value);			
				count++;
			}
			
		}
		
		//return last item of the 2d array, which is the optimal solution for the capacity
		return knapsackSolutions[safe.size()][capacity];
	}

	
	class Knapsack extends ArrayList<Item>
	{
		int value;
		int capacity;
		int currentSize;
		
		public Knapsack()
		{
			super();
			currentSize = 0;
			capacity = 0;
			value = 0;
		}
		
		public Knapsack(Knapsack k)
		{
			super();
			currentSize = k.currentSize;
			value = k.value;
		}
		
		public Knapsack(Knapsack k, Item i)
		{
			super();
			currentSize = k.currentSize + i.size;
			value = k.value + i.value;
		}
		
		public void setCapacity(int cap)
		{
			capacity = cap;
		}
		
		public boolean addItem(Item x)
		{
			if (currentSize + x.size <= capacity)
			{
				currentSize += x.size;
				value += x.value;
				add(x);
				
				return true;
			}
			else
				return false;
			
		}
		
	}
	
	class Item
	{
		int size;
		int value;
		String name;
		
		private Item(int vl, int sz, String nm)
		{
			value = vl;
			size = sz;
			name = nm;
		}
		
		public int getSize() {
			return size;
		}

		public int getValue() {
			return value;
		}
	}
	
}

//--------------The driver ---------------------------
public class ThiefDriver
{
	
	public static void main(String[] args) {
	    ///
	    /// Set up experiment:
	    ///
	    int INITIAL = 10 ;
	    int INCREMENT = 10 ;
	    ///
	    /// Create objects with add(NAME,SIZE,VALUE):
	    ///
	    Thief thief = new Thief();
	    thief.add("A",3,4) ;
	    thief.add("B",4,5) ;
	    thief.add("C",7,10) ;
	    thief.add("D",8,11) ;
	    thief.add("E",9,13) ;
	    ///
	    /// Run experiment:
	    ///
	    Thief.Knapsack knapsack;
	    for (int capacity=INITIAL ; capacity <= thief.safe.capacity ; capacity+=INCREMENT) {
	      System.out.println("Capacity = " + capacity) ;
	      thief.count = 0 ;
	      knapsack = thief.packRecursive(capacity) ;
	      System.out.println( "  Recursive value/COUNT: " + knapsack.value + " " + thief.count ) ;
	      thief.count = 0 ;
	      knapsack = thief.packMemoized(capacity) ;
	      System.out.println( "  Memoized value/COUNT: " + knapsack.value + " " + thief.count ) ;
	      thief.count = 0 ;
	      knapsack = thief.packDP(capacity) ;
	      System.out.println( "  DP value/COUNT: " + knapsack.value + " " + thief.count ) ;
	    
	    }
	  }