The Knapsack Max Profit

Question

There are 4 items: A weights 2LB has profit $40, B weights 5LB has profit $30, C weights 10LB has profit $50, and D weights 5LB has profit $10. Compute the maximum total profit you can take from any of the 4 items with a knapsack weight 16LB. You cannot take any portions of an item but the whole.

Please show how can the above problem be solved using knapsack problem approach.

Answer 1

A simple solution is to consider all subsets of items and calculate the total weight and value of all subsets. Then you should consider taking only the subsets that weighs less or equal to the capacity of your knapsack. From all such subsets, pick the maximum value subset.

To consider all subsets of items, there can be two cases for every item:

• the item is included in the optimal subset,
• the item is not included in the optimal subset.

Let's say the capacity of your knapsack is W. Therefore, the maximum value that can be obtained from n items is max of following two values.

1. Maximum value obtained by n-1 items and W weight (excluding the nth item)
2. Value of nth item plus maximum value obtained by n-1 items and W minus weight of the nth item (including nth item).

If weight of the nth item is greater than W, then the nth item can't be included and case 1 is the only option. This would be a naive approach and the solution would take 2ⁿ time.

Now for the overlapping subproblem:

weight = {2, 5, 10, 5}
Capacity = 16
The recursion tree would look like:       
// Here n,k -> items remaining, capacity remaining
// Going to left child -> including the item at hand
// Going to right child -> excluding the item at hand
                       _______4,16______    
                      /                 \   
                     /                   \
                  3,14                     3,16
                 /    \                    /   \
                /      \                  /     \
             2,9        2,14             2,5     2,16
              \          / \             \         / \
               \        /   \             \       /   \__
               1,9   1,4   1,14          1,5     1,6     1,16
              /\            /\          /\       /\        /  \
             /  \          /  \        /  \     /  \      /    \
           0,4  0,9      0,9  0,14    0,0 0,0  0,1  0,6   0,11   0,16

Since there are overlapping subproblems in the leaf, we can solve it using dynamic programming. If you store the values, it will be efficient to use them later. Here the match occurs in leaf nodes, if you take other examples, you'll see a match can occur far before the leaf nodes.

The pseudo-code would look like:

Procedure Knapsack(n, W):    //here, n = number of items, W = capacity of Knapsack
for i from 0 up to n
    for j from 0 up to W
        if i == 0 or j == 0
            table[i][j] :=0
        else if weight[i-1] <= j
            table[i][j] := max(profit[i-1] + table[i-1][w-weight[i-1]], table[i-1][j])
        else
            table[i][j] := table[i-1][j]
        end if
    end for
end for
Return table[n][W]