0
$\begingroup$

In classical 0-1 knapsack problem we have maximum allowed value for the weight - weight capacity.

Let's restrict total knapsack weight by min and max values

$$ M \leq \sum_{i=1}^{n}{w_i x_i} \leq W $$

Is there any known algorithm for this problem? Is there anything known which is better than brute force?

I failed to find anything about the given knapsack problem variation.

$\endgroup$
2
$\begingroup$

We can change the definition of the traditional Knapsack to "the maximum value we can get from the first n items using exactly W weight" instead of "the maximum value we can get from the first n using at most W weight". The easiest way to do this by replacing the following code:

for j from 0 to W do:
    m[0, j] := 0

from the Wikipedia article dynamic program pseudo code with

m[0, 0] := 0

Then we simply need to check for the maximum value of the range m[n, M] , ... , m[n, W].

$\endgroup$
  • $\begingroup$ thank you for the idea. I have changed the DP algorithm from Wikipedia to make it work in my case. You helped me greatly in doing this. $\endgroup$ – Victor Smirnov Jan 3 at 6:00

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.