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.
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].
