# Shrinking Item 0-1 Knapsack problem

I have encountered a variant of the knapsack problem with shrinking items.

Effectively, it is a 0-1 knapsack problem where the initial weight of each item is $$W(n)+V(n)$$ and their value is $$V(N)$$, but immediately after being put into the container the item shrinks by $$W(n)$$. This means that for every item IN the knapsack, weight and value are the same. (It is therefore also possible to look at this as a value-irrelevant "best fill only" 0-1 knapsack.)

So, in this case, one also needs to determine the proper order of items to insert and whether a specific item is legal in the combination before being put in the container.

I have already determined that order of insertion, given a valid collection, should be based on $$W(n)+V(n)$$ descending—but thus far I am failing to create a set of valid collections in anything under $$O(2^n)$$.

Dynamic programming solutions are failing me both because of the apparent interdependence of elements which makes memoization seemingly impossible.

I realize I have not given much here, but I could really use some help. How does one go about approaching this variant?

If curious, the actual application is that we have a large number of different electrical appliances that all cause a known power surge when turned on and afterwards draw a set amount of power. We never want to trip a breaker, so the surge needs to be taken into account when figuring out how many at most we can turn on.

• "The initial weight of each item is $W(n)+V(n)$ and their value is $V(N)$". Do you mean "the initial weight of the $n$-th item is $W(n)+V(n)$ and its value is $V(n)$"? May 31, 2019 at 10:35
• @Apass.Jack Yes, sorry, they are all different is what I meant :) May 31, 2019 at 13:03

Maybe I misunderstood you, but we can definitely find a dynamic programming solution, a very similar one to the one for knapsack itself. Let $$T[i, b]$$ denote the maximum profit that can be made for the first $$1 \leq i \leq n$$ items, and $$b$$ is the remaining weight of the knapsack. Here is the recurrence.

$$T[i, b] = \begin{cases} 0 & \text{if } i =0 \vee b = 0 \\ T[i - 1, b] & \text{if } w(i) > b \\ \max \{T[i - 1, b], T[i-1, b-V(i)] + V(i)\} & \text{if } w(i) \le b \end{cases}$$

For the base case, the 0th item doesn't exist so we have no profit. Similar for having run out of space.

Next, if $$w(i) := W(i) + V(i) > b$$, then we obviously cannot add item $$i$$ to our knapsack, and must continue on.

In the last case, we have two choices, either not include the item, or include it. For the latter, we then have $$b - V(i)$$ weight remaining, and $$V(i)$$ extra profit.

This dynamic programming algorithm has a running time of $$O(nB)$$, which is pseudopolynomial. Returning $$T[n, B]$$ is your maximum profit for all your items.

• This implies that the order of insertion does not matter? How can that be true? May 31, 2019 at 20:21
• I mean, would you get the same result no matter the initial order of elements? May 31, 2019 at 21:06