0

It's like

Maximum weight 3

Value Weight 

1955    1
2000    5
101     1

Take the first and the third. but can't find away to find total value. 1955+101.

i use Knapsack 0-1. is there anyway to find 1955+101 from the array

zeulb
  • 637
  • 1
  • 7
  • 23
  • 1
    Sure, you have to backtrack through the DP matrix and reconstruct the choices. There are tons of descriptions of that online. The disadvantage is that you'll need to keep the entire matrix around; if you didn't want this, you could save space by only keeping a small subset of the data. – Kerrek SB Dec 16 '11 at 17:29
  • can you tell me the algorithm ? i tried searching but find none – zeulb Dec 16 '11 at 17:33
  • Not off the top of my head, but think about it for yourself if you like... it should be The Obvious Thing. Otherwise try Wikipedia; I'm fairly sure that has it (at least the article on the Longest Common Subsequence has the analogous code). – Kerrek SB Dec 16 '11 at 17:37
  • 1
    possible duplicate of [How to find which elements are in the bag, using Knapsack Algorithm \[and not only the bag's value\]?](http://stackoverflow.com/questions/7489398/how-to-find-which-elements-are-in-the-bag-using-knapsack-algorithm-and-not-onl) – amit Dec 16 '11 at 17:57
  • @zeulb [this question](http://stackoverflow.com/questions/7489398/how-to-find-which-elements-are-in-the-bag-using-knapsack-algorithm-and-not-onl) shows how to find the exact elements that give you the best solution for the knapsack problem, from the constructed matrix. – amit Dec 16 '11 at 17:59

1 Answers1

0

lets say that you have 2 arrays values and wt, and another variable initial_capacity which is the max capacity of the knapsack. Then the you need to first call the dp function first which computes the maxValue you can achieve. The reconstruct function tells you which items you should take in order to achieve maxValue.

int dp(int position, int weight)
{
    if(position == no_of_items) return 0;
    if(mem[position][weight] != -1) return mem[position][weight];

    int r1 = dp(position + 1, weight);
    int r2 = dp(position + 1, weight - wt[position]) + value[position];

    return mem[position][weight] = max(r1, r2);
}

void reconstruct(int position, int weight)
{
    if(position == no_of_items) return;

    int r1 = dp(position + 1, weight);
    int r2 = dp(position + 1, weight - wt[position]) + value[position];

    if(r2 > r1)
    {
        cout << "Take item at position : " << position << endl;
        reconstruct(position + 1, weight - wt[position]);
    }
    else
    {
        reconstruct(position + 1, weight);
    }
}

int main()
{
    //read input here
    memset(mem, -1);
    int maxValue = dp(0, initial_capacity);
    cout << "Max value : " << maxValue << endl;
    reconstruct(0, initial_capacity);
}

Note that reconstruct works in a greedy way. Which ever decision (take the item or skip the item) leads to maxValue, it will take that decision. If your decision involves taking a particular item, you print the index of that item.

Hope this helps :)

Purav Shah
  • 523
  • 1
  • 4
  • 13