Help with dynamic programming, knapsack problem
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 2 of 2

Thread: Help with dynamic programming, knapsack problem

Hybrid View

  1. #1
    Join Date
    Sep 2010
    Posts
    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}

  2. #2
    Join Date
    Sep 2010
    Posts
    3

    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
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center