1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ "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)$"? $\endgroup$ – Apass.Jack May 31 at 10:35
  • $\begingroup$ @Apass.Jack Yes, sorry, they are all different is what I meant :) $\endgroup$ – Weckar E. May 31 at 13:03
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This implies that the order of insertion does not matter? How can that be true? $\endgroup$ – Weckar E. May 31 at 20:21
  • $\begingroup$ I mean, would you get the same result no matter the initial order of elements? $\endgroup$ – Weckar E. May 31 at 21:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.