Bounded subset sum

Question

I have a question about a variant subset-sum problem.

In a set S = {N1, N2, N3... Ni}, each element can be selected multiple time with upper limit = { L1, L2, L3... Li}. And the question is, what is the most efficient algorithm to find one subset from S, such that the subset sum <= Wi (0 <= Wi) and it's also the maximum sum.

It's like a value independent bounded knapsack problem. I know when all the element's limits are all 1, it can be solved in pseudo-polynomial time. But I wonder is there a pseudo-polynomial algorithms for this kind of variant subset sum problem? Thank!

What if you "unroll" the limits, i.e. instead of S={1,2}, L={2,2}, use S={1,1,2,2}, L={1,1,1,1} and then use the algorithms for limits of 1? — tobias_k
But how about the value in S is not constant, instead it depends on how many items I choose from that particular element. Normally, when i choose n items from N1, the value will just be nN1. But if it's actually a function like nN1 + b. In this scenario, it seems like it can not be solved just by flatten the set S. — Kyle

eldar eldar · Accepted Answer · 2019-11-22T01:59:20

As correctly pointed out in the comments, the problem as it stands can be solved by the same 0-1 knapsack algorithm, just by creating as many items of each type as the amount of times you are allowed to use it.

However, you introduce a twist that disallows this, so let's consider this more general problem: you have a set of {N1, N2, ..., Nk} elements, and for each Ni you know the number of times Li you could select this element, but the cost function is an arbitrary f(i, j), where i is element index and j is the number of times we selected it. (So, for example, the cost function corresponding to the original problem is f(i, j) = Ni * j) And, if I understand correctly, you are simply trying to find the maximum possible sum of cost function values that's below a certain value W.

Let's define a function isPossible(i, sum) that answers whether it's possible to select some combination of the first i elements (with each of them taken at most as many times as permitted) and achieve the sum sum. The initial values are isPossible(0, 0) = True, isPossible(0, s>0) = False: by using the first 0 elements (i.e, no elements at all), we can only obtain the sum 0.

Now let's iterate over elements in increasing order of their index, and also iterate over how many times we are going to use the specific element, and update the values in isPossible accordingly:

for i in 0..k-1:
  for j in 0..Li:
    for w in 0..W - f(i, j):
      if isPossible[i][w]:
        isPossible[i+1][w + f(i, j)] = True

In English: if we were able to obtain the sum w by using the first i elements, we should be able to obtain the sums w+f(i, 0), w+f(i, 1), ..., w+f(i, Li) using the first i elements and Ni some number of times - as long as they all fall under W.

(Note that the algorithm needs some tweaking if the cost function can have negative values - we can't assume that the range of allowed intermediate sums is [0, W] anymore.)

This is obviously still pseudo-polynomial, but it's much smaller than the usual knapsack because we have to iterate over the number of times we use each item.

Bounded subset sum

1 Answers