Bounded knapsack special case - small individual item weight is small compared to the number of items

Question

For the bounded knapsack problem, assuming the value of each item is the same as its weight and all weights are positive integers, I am wondering if there is an optimisation for the case where individual item weight is small compared to the number of items n and the capacity of the knapsack is half the sum of all item weights? e.g. 100k items and each item weight is restricted to [1, 10].

The algorithm should give exact solution. I am aware of the O(n*W) time and O(W) space DP algorithm but thought there might be better ways to solve it in this case. Thanks in advance.

This is from an algo challenge and the O(n*W) time solution was functionally correct but not fast enough (a magnitude slower than what was required). And I can't seem to find anything on this problem. The input is a list of item weights and required output is the maximum total value of items that can be fitted into the knapsack.

Answer 1

The paper you're looking for is Pisinger 1999, "Linear Time Algorithms for Knapsack Problems with Bounded Weights". It's a bit of a pain though because the pdf seems to have lost the distinguishing markings on some of the variables.

Add the items to your solution in any order until you reach an item b - the break item - which causes you to exceed W. The items 1, 2, ... b-1 constitute a balanced filling, and all other balanced fillings are those that can be reached by a series of two operations:

• A balanced insert is the addition of an item at b or beyond to a balanced solution with weight <= W.
• A balanced remove is the removal of an item before b from a balanced solution with weight > W.

It's pretty easy to see two things: first that all balanced solutions are within 10 units of weight of W, and second that an optimal solution must be a balanced solution.

We find our way from the initial solution to the optimal one by dynamic programming.

• For each item t from b onwards,
• and for each weight w such that W - 9 < w < W + 10,
• we're going to keep track of the most recent item s before b
• such that there's a balanced filling of weight w which can be reached through adding/removing items solely between s and t

Read that through a couple of times. Notice that some point along the way, we're guaranteed to run into an optimal solution (though we won't know it until the end). Letting wBreak be the weight before the break item is added, our algorithm is intitalized with:

for (w = W-9, w <= W, w++) { s(b-1, w) = 0 }
for (w = W+1, w <= W+10, w++) { s(b-1, w) = 1 }

s(b, wBreak) = b - 1

These are all defaults, apart from s(b, wBreak). Then we get to the meat:

for (t = b, t <= N, t++) 
{
    for (w = W-9, w <= W, w++) 
    {
        // Trying adding item t to the solutions with weight <= W 
        s(t, w + w_t) = max( s(t-1, w), s(t-1, w + w_t) )   
    }
    for (w = W+10, w > W, w--)
    {
        // Removing as many items as needed to get back to a balanced filling
        for (j = s(t, w) - 1, j >= s(t-1, w), j--) 
        {
            s(t, w - w_j) = max( s(t, w - w_j), j )
        }
    }
}

In all, this takes O(N) time, and we can identify the weight of the optimal filling as the nontrivial s(t,w) with w closest to W yet no larger than it.

Note this doesn't take advantage of the fact that the sum of the weights of all items is 2W. I'll try and think of a simplification using that, but it might be the question setters added that so you don't have to worry about the trivial edge cases when there's not enough items to fill W.

Answer 2

The Pisinger 1999 paper Bounded Knapsack can be found at http://www.diku.dk/~pisinger/94-27.ps and the implemented code at http://www.diku.dk/~pisinger/codes.html as bouknap.c