The Integer (0/1) Bounded Knapsack Problem

Quoting the problem statement from Petr's blog:

"The bounded knapsack problem is: you are given n types of items, you have u_i items of i^th type, and each item of i^th type weighs w_i and costs c_i. What is the maximal cost you can get by picking some items weighing at most W in total?"

Here, we assume that the knapsack can hold a weight at most W.

We shall describe 3 solutions to this problem, each of which reduces the complexity of the solution by a certain amount.

1. O(W*n*M): The first solution is the standard knapsack solution solution, which just involves copying each item instance of every item type to get a total of u_i items of the i^th type, each of which represents a different item having the same w_i & c_i as the item of the i^th type.
   
   It is easy to see that if we have a mean of M number of items of each type, the complexity of this solution is O(W * n * M)
2. O(W*n*log(M)): The second solution involves rewriting items such that we have a fewer number of items of each type to work with. We shall then solve the transformed problem using the same technique as the standard knapsack problem (as in the solution above).
   
   Suppose we have 21 instance of the i^th item type, weighing w_i and costing c_i. We observe that 21 can be rewritten (using powers of 2) as:
   21 = 1 + 2 + 4 + 8 + 6
   
   We basically add powers of 2 till we exceed the sum we want to create (21 in this case). When we exceed the sum, we just add the difference (6 in this case) between the number (21 in this case) and the current sum we have (15 in this case = 1+2+4+8).
   
   Now, the new items are created by combining 1, 2, 4, 8, and 6 items of the original instances. These newly created items will have the following weights and costs:
   
   

   Number of items of the original type combined	Weight	Cost
   1	1*wi	1*ci
   2	2*wi	2*ci
   4	4*wi	4*ci
   8	8*wi	8*ci
   6	6*wi	6*ci

   
   
   Hence, we have effectively reduced the number of items from 21 to 5. In general, we replace the M in the solution above with log(M) to get a final complexity of O(W * n * log(M)).
3. O(W*n): The third and most efficient solution to this problem is the one that took me almost 3 days to figure out and understand. The short post on petr's blog actually contains all the information needed to understand it, but I'm not that comfortable reading terse explanations; especially when it's a new idea, so here is something more verbose.
   
   There is also a paper and a section in a book dedicate to this problem, but I find them quite hard as well.
   
   Let's assume that this row (in the DP table of Items (rows) v/s Weight (columns)) represents the best configuration (maximum cost) for the knapsack at every weight 0 .. W that includes all item types from 1 .. (k-1)
   
   

   Weight	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
   Item (k-1)	0	5	5	7	15	15	19	20	21	23	30	33	42	42	49	51

   
   
   So, the basic observation is that DP_{(k-1), w} represents the best solution including all items from 1 .. (k-1) (both inclusive) with a knapsack of weight (w).
   
   To compute DP_{k, w}, we consider the possibility of including either 0, 1, 2, 3, 4, ..., u_i items of the i^th type to the previous best solution including all items from 1 .. (k-1). This gives us the following recurrence:
   
   DP_{k, w} = max (
       DP_{(k-1), w},
       DP_{(k-1), w-1*wk} + 1*c_k,
       DP_{(k-1), w-2*wk} + 2*c_k,
       DP_{(k-1), w-3*wk} + 3*c_k,
       ...,
       DP_{(k-1), w-ui*wk} + u_i*c_k)
   
   An interesting observation here would be that we only deal with every w_k^th element from the previous array to decide on any element in the current array.
   
   Let us for a minute ignore the fact that we have only a fixed number of items of each type and instead assume that we have an infinite number of items of each type. Let us assume that item i weighs 3 and costs 9. If we make that assumption, we see that the best solution at DP_{k, 12} is represented by taking the maximum of the cells colored in green below.
   
   

   Weight	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
   Item (k-1)	0	5	5	7	15	15	19	20	21	23	30	33	42	42	49	51
   	36			34			37			32			42

   
   
   What we have essentially done is added:
   0*9 to DP_{(k-1), 12}
   1*9 to DP_{(k-1), 9}
   2*9 to DP_{(k-1), 6}
   3*9 to DP_{(k-1), 3} and
   4*9 to DP_{(k-1), 0}
   
   The problem has reduced to finding the maximum value among all the values of the array that is formed by picking every w_k^th element from the previous best solution and adding some multiple of c_k to it.
   
   We also notice that it doesn't matter what values we add to DP_{(k-1), w} (for the k^th item) as long as they are c_k apart. Hence, if the weight of the knapsack is W and the weight of the k^th item is w_k, we can add the following to every w_k^th element in the previous array.
   
   

   Column to which value is added	Value Added
   0	(W/wk)*ck
   1*wk	(W/wk - 1)*ck
   2*wk	(W/wk - 2)*ck
   3*wk	(W/wk - 3)*ck

   
   If we now reintroduce the requirement that each item type will have only a bounded or fixed number of instances (i.e. u_k is bounded), then the problem reduces to finding the maximum value in every window of size u_k in the array we just computed. This can easily be done by pre-processing the array to maintain the largest element in every window of size u_k.
   
   However, the actual value of the cost at any cell needs to be computed by adding back any differential that we may have subtracted to ensure that every entry is c_k apart and that the first entry is the one which has the maximum multiple of c_k subtracted from it. For the j^th array element in the current sub-array we are processing, this value will be (W/w_k - j)*c_k (since we have subtracted that much extra from those elements, we must now add it back).
   
   Hence, we can safely say that we shall have w_k different sub-problems that we shall try to solve assuming that we can use a single computation for every w_k^th element.
   
   This allows us to find the value at every cell of the (k x W) matrix is amortized time O(1) (we have amortized the cost of pre-computing the w_k arrays across all the element accesses). This makes the total running time of this algorithm O(W * n).