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?

This problem is apparently reasonably popular, and there are many articles about it. However, most of those seem to be interested in approximate solutions or performance on random inputs. But what if we want to treat it as a usual algorithm problem - what is the best possible worst-case running time for solving it?

The best algorithm I could find on the Internet has complexity O(W*n*log(max(u_{i})). It goes like this: instead of having u_{i} items of type i, we create several new types that are multiples of type i, for example items with weight 2*w_{i} and cost 2*c_{i}, then the same for 4 and so on, and declare that we have just one item of each type. We create the new types in such a way that the number of new types is logarithmic, and anything that was possible to represent using the old items is also representable using the new items and vice versa. We get a 0-1 knapsack problem with n*log(max(u_{i}) types which leads to a dynamic programming solution with the above complexity.

However, when this problem was given at a Codeforces contest yesterday, several people came up with a O(W*n) solution for this problem. First, we start with the standard dynamic programming solution: let dp_{k,w} be the best cost that we can get by packing the total weight of w using the first k item types. Each new type is then handled as follows: dp_{k,w}=min(dp_{k-1,w}, dp_{k-1,w-wk}+c_{k}, ..., dp_{k-1,w-uk*wk}+u_{k}*c_{k}). This dynamic programming has O(W*n) states, and each state is processed in O(max(u_{i})).

But we can process each state in O(1) amortized time! Let's take a look at the above recurrence. First, we notice that we can separate all values of w into w_{k} groups, based on the remainder of division on w_{k}, and those groups can be handled separately. Then, for each group, the problem we need to solve is to find min(a_{i}, a_{i-1}+c, a_{i-2}+2*c, ..., a_{i-k}+k*c). By setting b_{i}=a_{i}-i*c, this expression is transformed into min(b_{i}+i*c,b_{i-1}+(i-1)*c+c, ...), which is just i*c+min(b_{i}, b_{i-1}, ..., b_{i-k}). Thus our problem is reduced to finding minimums of groups of k+1 consecutive numbers in a given array.

And this, in turn, is a well-known problem that is solvable in O(size of array) using one of the two methods: we can either maintain a sequence of incremental (from the end) minima for a segment of size k+1 and update it quickly when we shift one position to the right, or we can just separate the entire array into blocks of size k+1, and calculate the prefix and suffix minima for each block - this allows to find the minimum for any block of size k+1 by splitting it into two blocks with precomputed answers.

Is it well-known that bounded knapsack is solvable in O(W*n) worst-case?

Petr , Can you give link to screencast 2.0 , I cannot access torrents in my college.

ReplyDeleteAnd previous links seems to have died out. I saw SRM 500, It was awesome.

Can I get SRM 502 screencast?

I've tried to de-mistify this approach - here is the blog post detailing it: http://dhruvbird.blogspot.com/2011/09/integer-01-bounded-knapsack-problem.html

ReplyDeleteFor this problem ( http://codeforces.com/problemset/problem/95/E ), I don't understand how taking min() for the knapsack DP will solve it. Please could someone explain with an example?

ReplyDeleteI think in the post it should be max, as the optimal value is maximum cost.

DeleteSeems to have been known since 1999, at least: http://www.springerlink.com/content/6vwed32pkyf4df6k/

ReplyDeleteThere is an open description available here: http://books.google.com/books?id=u5DB7gck08YC&lpg=PA211&pg=PA194#v=onepage&q&f=false

Wow, thanks! This is looks like exactly this problem and the first algorithm for finding running minima described above.

ReplyDelete"... We create the new types in such a way that the number of new types is

ReplyDeletelogarithmic, and anything that was possible to represent using the old

items is also representable using the new items and vice versa".

Can you give a rough idea how to do this ?.. directly taking the powers of 2 of all set bits wont work. Thanks.

Please could anyone explain the intuition behind the O(W*n) solution? I'm not able to fully understand how it works.

ReplyDeleteIt is quite not new to me. Years ago, I posted this problem in http://vn.spoj.pl/problems/DTTUI2/ (in Vietnamese) and many high school student surprised me by giving the above (W*n) solution.

ReplyDelete".. directly taking the powers of 2 of all set bits wont work", why not??

ReplyDeleteThis trick was published in the editorial for the XII Polish Informatics Olympiad (www.oi.edu.pl)... about 6 years ago.

ReplyDeleteWell, you can try it like this. Just take the powers of 2 until its smaller or equal to the remainder. For example for u=25 ,

ReplyDeleteTake 1 remainder 25

Take 2 remainder 23

Take 4 remainder 19

Take 8 remainder 11

Can't take 16 because its bigger than 11.

So the items should be w, 2w, 4w,8w and 11w. With this coins you can make any amount between 1 and 26, right?

Sorry, u=26

ReplyDeletebut what if the number is a power of 2 ? I don't see how is this possible

ReplyDeleteI guess in this case allowing the first type (w) to have 2 items,,and proceeding as you did but with (2^n)-1 will do the trick. but then we should keep track for each type whether it has only one item or 2..same complexity..

or what do you think ?

If its a power of 2 say 2^n, then the break-up would be 1, 1, 2, 4, ... , 2^(n-1)

ReplyDeleteIn youy 2nd last paragraph what ai represents ...

ReplyDeleteAre there any O(N*W) solution in http://codeforces.com/contest/95/status/E , Can you show me where it is ?

ReplyDeleteAlso in practice it seems O(N*W*log(max(ui))) is faster

Nice trick. I didn't knew it before, thanks for the post. If possible, please also write such interesting posts more frequently for the problems you solve correctly in contests, rather than on the ones your code failed in contests.

ReplyDeleteNo idea whether this was published as a paper, but it is most likely well known -- in contests I've already seen several tasks that required this trick.

ReplyDelete