3
$\begingroup$

I am trying to understand the DP solution to the basic knapsack problem.However even after reading through a variety of tutorials ,its still beyond my comprehension.I am taking an algorithmics course and need to solve questions based on the classic knapsack problem.However unless I understand the classic problem clearly , I won't be able to make any headway to the advanced ones.Please help pointing me out in the right direction.

The recursive equation is way too confusing for me.

$\endgroup$
  • 2
    $\begingroup$ What exactly is it the part that you getting stuck on? $\endgroup$ – lPlant Jun 26 '14 at 20:00
  • $\begingroup$ I don't understand how the recursive equation yields the solution.We take the maximum of the solution where ith item is used and where ith is not used.How does that help in finding the solution. $\endgroup$ – user48833 Jun 26 '14 at 20:06
  • 2
    $\begingroup$ Because either the $i$th item is part of the solution or it isn't. So the best solution is either the $i$th item plus the best you can do with all the other items, or it's just the best you can do with all the other items. $\endgroup$ – David Richerby Jun 26 '14 at 20:12
8
$\begingroup$

The key to understanding a dynamic programing problem is understanding the recursive definition and this can be daunting. For this problem we start with n objects labeled 1 to n.

We define $O(K,W)$ to be the optimal value for the first k items with a total weight W, we need to be able to define this in terms of subproblems now since without that, dynamic programming does not work. To add some quick definitions $W_k$ is the weight of the kth item and $V_K$ is its values.

So we define the recursive formula in 2 cases:

The first case is $O(K,W) = O(K-1,W) \quad \text{if $W_k$>W}$, meaning the k'th item weighs more then are target weight so it cannot be added even if nothing else was in the bag.

The second case is the decision case, $O(K,W) = MAX(O(K-1,W),O(K-1,W-W_k)+V_k)$ it means that either we don't add Item K to our set, in which case our best so far is $O(K-1,W)$, or we do add it, in which case we only have $W-W_k$ weight remaining to be filled with items 1 to k-1 and our total value is $O(K-1,W-W_k)+V_k$, which is our recursive value plus the value of the new Item.

The optimal solution is then $O(n,MaxWeight)$

Now for the dynamic programing part, the best way to start out is with our standard grid, we have our horizontal portion as k, so at any $i$ point we have the first $i$ items available, and our vertical as the total weight from zero to the weight the question was asking. The first row and columns will have a value of zero since with no weight or items, our bag has no value. Below I have put good walk through example. We walk through the algorithm by moving down each column, one column at a time. So at any grid location we check 3 other grid points which correspond to the values from the recursive definition, If we are at grid point $k,W$ and item k has a weight of$W_k$ and a value of $V_K$ we first check if $W<W_K$, if it is we use the square above it, since our item is too big, this is $O(K-1,W)$, if the item is not too big you check locations $k-1,W$ which is $O(K-1,W)$ and compare it to $K-1,W-W_k$ which is $O(K-1,W-W_k)+ V_k$, since we are going column by column from smallest to largest these are already calculated. If we keep doing this we will eventually get to the bottom right corner, which is the solution to the problem. The trick to this is we start at the smallest values and save the answers so for larger one the recursion is only a quick lookup instead of a full call.

enter image description here

$\endgroup$
  • 1
    $\begingroup$ The grid helped me a lot to understand the knapsack problem.I know understand how traversing from the lowest to the highest yields the solution.However if we have additional constraints such as the number of elements that can be in the sack, we would have a 3D dimensioinal grid here?and then if we need to find the maximum capacity with k elements we will just look up for the values in the k3rd dimension.I am not sure if it makes sense or not. $\endgroup$ – user48833 Jun 26 '14 at 21:13
  • $\begingroup$ @user48833 The 3D approach to deal with a limited number of items should work. $\endgroup$ – FrankW Jun 27 '14 at 7:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.