Dynamic Programming Solution to 0,1 KnapSack Problem

Problem Detail: 

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.

Asked By : user48833

Answered By : lPlant

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/28001