CODEWITHSUNDEEP
algorithmdynamic-programmingmathematical-optimizationdiscrete-mathematics
maplemaple
maplemaple

Reputation: 1715

algorithm about unbound knapsack problem with possible negative weights?

I meet an unbounded knapsack problem with possible negative weights: There are k items, with weights x1, x2, ..., xk (xi can be positive or negative). Every item can have infinite number. The bag can store weight W > 0. How to store as little number as possible with exact W weight, if there is no solution just return -1.

That is

enter image description here

What's the algorithm to solve this problem?

Firstly, we cannot drop negative one. For example, x_1 = 3, x_2 = -1, W = 2. If we drop negative one, there can be no solution. However, there can be solution n_1=1, n_2=1.

The naive idea of dynamic programming/recursion with memorization cannot handle negative weight with infinite number.

dp[i][w] = minimum number of items to fill weight w by using item 1, 2, ..., i

dp[i][w] = min(dp[i-1][w], dp[i][w - xi] + 1)

Since xi can be negative and infinite number, there can be infinite state dp[i][w].

Upvotes: 1

Views: 702

Answers (1)

Matt Timmermans
Matt Timmermans

Reputation: 59233

You can do a breadth-first search on the graph of achievable total weights, where there exists an edge from weight w to weight v if there is an item with weight v-w. Start at 0 and find the shortest path to W.

The trick is that you don't need to consider achievable weights less then -max(|xi|) or greater than W+max(|xi|). You don't need to consider anything else, because for every sequence of item weights that adds up to W, there is an order in which you can perform the additions so that the intermediate sum never goes outside those bounds.

Assuming that the weights are integers, this makes the graph finite.

Upvotes: 5

Related Questions