# 0-1 knapsack problem with minimum and maximum weight capacity

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

• 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. Jan 3, 2020 at 6:00