Limited satchel bag - small individual product weight is small compared to the number of items

Question

For the problem of a limited backpack , assuming that the value of each element coincides with its weight, and all the weights are positive integers, I wonder if there is optimization for the case when the individual weight of the element is small compared to the number of elements n and the backpack capacity is half the amount all item weights? for example, 100 thousand units and each item’s weight is limited [1, 10].

The algorithm should give an exact solution. I know O (n * W) time and O (W) space DP algorithm, but I thought that in this case there may be better ways to solve it. Thanks in advance.

This is from an algo call, and the O (n * W) time solution was functionally correct, but not fast enough (the value is slower than required). And I can not find anything on this issue. The input is a list of item weights and the required output is the maximum total number of items that can be installed in a backpack.

Answer 1

The paper you are looking for is Pisinger 1999, "Linear time algorithms for knapsack problems with limited weights." This is a bit of a pain, though due to the fact that pdf seems to have lost the distinctive markings of some variables.

Add the elements to your solution in any order until you reach the b element - break item - which will exceed W. Elements 1, 2, ... b-1 make up a balanced filling , and all other balanced fillings are those that can be achieved through a series of two operations:

• A balanced insertion is adding an element to b or higher in a balanced solution with a weight <= W.
• A balanced removal is the removal of an element up to b from a balanced solution with a weight> W.

It is very easy to see two things: firstly, all balanced solutions are within 10 units of weight W, and secondly, the optimal solution should be a balanced solution.

We find a way from the original solution to the optimal one through dynamic programming.

• For each element t from b,
• and for each weight , so W - 9 <w <W + 10,
• we will track the most recent items s to b
• so that there is a balanced filling of the weight w, which can be achieved by adding / removing elements exclusively between s and t

Read it a couple of times. Please note that at some stage we guarantee that we will get the optimal solution (although we will not know it until the end). If wBreak is weighted before the break element is added, our algorithm will be laid out as follows:

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 default values ​​except 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 general, this takes O (N) time, and we can determine the weight of the optimal filling as nontrivial s (t, w), and w, the closest to W, is not even larger.

Please note that this does not use the fact that the sum of the weights of all elements is 2 watts. I will try to come up with a simplification using this, but may have added that you do not need to worry about trivial cases of the edge when there are not enough elements to fill W.

Answer 2

The Pisinger 1999 document limited to a backpack 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