CODEWITHSUNDEEP
algorithmknapsack-problem
sanderd17
sanderd17

Reputation: 420

Dual knapsack algorithm

Say you have a warehouse with fragile goods (f.e. vegetables or fruits), and you can only take out a container with vegetables once. If you move them twice, they'll rot too fast and cant be sold anymore.

So if you give a value to every container of vegetables (depending on how long they'll still be fresh), you want to sell the lowest value first. And when a client asks a certain weight, you want to deliver a good service, and give the exact weight (so you need to take some extra out of your warehouse, and throw the extra bit away after selling).

I don't know if this problem has a name, but I would consider this the dual form of the knapsack problem. In the knapsack problem, you want to maximise the value and limit the weight to a maximum. While here you want to minimise the value and limit the weight to a minimum.

You can easily see this duality by treating the warehouse as the knapsack, and optimising the warehouse for the maximum value and limited weight to a maximum of the current weight minus what the client asks.

However, many practical algorithms on solving the knapsack problem rely on the assumption that the weight you can carry is small compared to the total weight you can chose from. F.e. the dynamic programming 0/1 solution relies on looping until you reach the maximum weight, and the FPTAS solution guarantees to be correct within a factor of (1-e) of the total weight (but a small factor of a huge value can still make a pretty big difference).

So both have issues when the wanted weight is big.

As such, I wondered if anyone studied the "dual knapsack problem" already (if some literature can be found around it), or if there's some easy modification to the existing algorithms that I'm missing.

Upvotes: 3

Views: 2090

Answers (1)

j_random_hacker
j_random_hacker

Reputation: 51226

The usual pseudopolynomial DP algorithm for solving knapsack asks, for each i and w, "What is the largest total value I can get from the first i items if I use at most w capacity?"

You can instead ask, for each i and w, "What is the smallest total value I can get from the first i items if I use at least w capacity?" The logic is almost identical, except that the direction of the comparison is reversed, and you need a special value to record the possibility that even taking all i of the first i items cannot reach w capacity -- infinity works for this, since you want this value to lose against any finite value when they are compared with min().

Upvotes: 3

Related Questions