## Saturday, July 9, 2011

### Integral bounded knapsack problem solvable in O(knapsack_size*num_of_items)

The bounded knapsack problem is: you are given n types of items, you have ui items of i-th type, and each item of i-th type weighs wi and costs ci. 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(ui)). It goes like this: instead of having ui items of type i, we create several new types that are multiples of type i, for example items with weight 2*wi and cost 2*ci, 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(ui) 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 dpk,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: dpk,w=min(dpk-1,w, dpk-1,w-wk+ck, ..., dpk-1,w-uk*wk+uk*ck). This dynamic programming has O(W*n) states, and each state is processed in O(max(ui)).

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 wk groups, based on the remainder of division on wk, and those groups can be handled separately. Then, for each group, the problem we need to solve is to find min(ai, ai-1+c, ai-2+2*c, ..., ai-k+k*c). By setting bi=ai-i*c, this expression is transformed into min(bi+i*c,bi-1+(i-1)*c+c, ...), which is just i*c+min(bi, bi-1, ..., bi-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?

1. Petr , Can you give link to screencast 2.0 , I cannot access torrents in my college.
And previous links seems to have died out. I saw SRM 500, It was awesome.
Can I get SRM 502 screencast?

2. 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

3. For 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?

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

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

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

6. "... 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".

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

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

8. NguyenxuankhanhmMay 10, 2013 at 1:37 PM

It 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.

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

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

11. Well, 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 ,
Take 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?

12. Sorry, u=26

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

I 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 ?

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

15. In youy 2nd last paragraph what ai represents ...

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

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

17. 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.

18. No 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.