Shrinking Item 0-1 Knapsack problem

Question

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.

Answer 1

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.