DP algorithm for bounded Knapsack?

Question

The Wikipedia article about Knapsack problem contains lists three kinds of it:

1. 1-0 (one item of a type)

2. Bounded (several items of a type)

3. Unbounded (unlimited number of items of a type)

The article contains DP approaches for 1. and 3. types of problem, but no solution for 2.

How can the dynamic programming algorithm for solving 2. be described?

Answer 1

The other DP solutions mentioned are all suboptimal as they require you to directly simulate the problem, resulting in a O(number of items * maximum weight * total count of items) runtime complexity.

There are many ways to optimize this, and I'll mention a few of them here:

---

One solution is to apply a technique similar to Sqrt Decomposition and is described here: https://codeforces.com/blog/entry/59606. This algorithm runs in O(number of items * maximum weight * sqrt(maximum weight)).

---

However, Dorijan Lendvaj describes a much faster algorithm that runs in O(number of items * maximum weight * log(maximum weight)) here: https://codeforces.com/blog/entry/65202?#comment-492168

Another way to think of the above approach is the following:

For each type of item, let's define the following values:

• w, the weight/cost of the current type of item
• v, the value of the current type of item
• n, the number of copies of the current type of item available to use

Phase 1

First, let us consider 2^k, the largest power of 2 less than or equal to n. We insert the following items (each inserted item is in the format (weight, value)): (w, v), (2 * w, 2 * v), (2^2 * w, 2^2 * v), ..., (2^(k-1) * w, 2^(k-1) * v). Note that the items inserted each represent 2^0, 2^1, ..., 2^(k-1) copies of the current type of item respectively.

Observe that this is the same as inserting 2^k - 1 copies of the current type of item. This is because we can simulate the taking of any number of items (represented as n') by taking the combination of the above items that corresponds to the binary representation of n' (For all whole numbers k', if the bit representing 2^k' is set, take the item that represents 2^k' copies of the current type of item).

Phase 2

Lastly, we just insert the items that correspond to the set bits of n - (2^k - 1). (For all whole numbers k', if the bit representing 2^k' is set, insert (2^k' * w, 2^k' * v)).

Now, we can simulate the taking of up to n items of the current type simply by taking a combination of the above inserted items.

I don't currently have an exact proof of this solution, but after playing around with it for a while it seems correct. If I can figure one out I may update this post later on.

Proof

First, a proposition: All we have to prove is that inserting the above items allows us to simulate the taking of any number of items of the current type up to n.

With that in mind, let's define some variables:

• Let n be the number of items of the current type available
• Let x be the number of items of the current type we want to take
• Let k be the greatest integer such that 2^k <= n

If x < 2^k, we can easily take x items using the method described in phase 1 of the algorithm:

... we can simulate the taking of any number of items (represented as n') by taking the combination of the above items that corresponds to the binary representation of n' (For all whole numbers k', if the bit representing 2^k' is set, take the item that represents 2^k' copies of the current type of item).

Otherwise, we do the following:

Take n - (2^k - 1) items. This is done by taking all the items inserted in phase 2. Now only the items inserted in phase 1 are available for use.

Take x - (n - (2^k - 1)) items. Since this value is always less than 2^k, we can just use the method used for the first case.

Finally, how do we know that x - (n - (2^k - 1)) < 2^k?

If we simplify the left side, we get:

x - (n - (2^k - 1)) x - n + 2^k - 1 x - (n + 1) + 2^k

If the above value was >= 2^k, then x - (n + 1) >= 0 would be true, meaning that x > n. That would be impossible as that's not a valid value of x.

---

Finally, there is even an approach mentioned here that runs in O(number of items * maximum weight) time.

The algorithm is similar to the brute force method ic3b3rg proposed and just uses simple DP optimizations and sliding window deque to bring down the run time.

My code was tested on this problem (classical bounded knapsack problem): https://dmoj.ca/problem/knapsack

My code: https://pastebin.com/acezMrMY

Answer 2

Use the 0-1 variant, but allow repetition of an item in the solution up to the number of times specified in its bound. You would need to maintain a vector stating how many copies of each item you already included in the partial solution.