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?

18 comments:

  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?

    ReplyDelete
  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

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

    ReplyDelete
  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

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

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

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

    ReplyDelete
  8. Nguyenxuankhanhm10 May, 2013 11:37

    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.

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

    ReplyDelete
  10. Piotr Zielinski10 May, 2013 11:37

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

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

    ReplyDelete
  12. Loai Ghoraba10 May, 2013 11:37

    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 ?

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

    ReplyDelete
  14. In youy 2nd last paragraph what ai represents ...

    ReplyDelete
  15. 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

    ReplyDelete
  16. 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.

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

    ReplyDelete