Question: I'm very new to programming and have been asked to solve a program for work. Right now we are dealing with a typical 0/1 Knapsack problem, in which the benefit/value is maximized given mass and volume constraints. 

My task is to basically reverse this and minimize either the volume or mass given a value constraint. In other words, I want my benefit score to be greater than or equal to a set value and then see how small I can get the knapsack given that threshold value. 

I have tried researching this problem elsewhere and am sure that it probably has a formal name, however I am unable to find it. If anyone has any information I would greatly appreciate it. I am at a bit of a loss of how to go about solving this type of algorithm as you cannot use the same recursion formulas.

Answer: 
Let's call the weight of item i w(i), and its value v(i). Order the items arbitrarily, and define f(i, j) to be the minimum possible capacity of a knapsack that holds a subset of the first i items totalling at least a value of j.

To calculate f(i, j), we can either include the ith item or not in the knapsack, so

```
f(i>0, j>0) = min(g(i, j), h(i, j))      # Can include or exclude ith item; pick the best
f(_, 0) = 0                              # Don't need any capacity to reach value of 0
f(i<=0, j>0) = infinity                  # Can't get a positive value with <= 0 items

g(i, j) = f(i-1, j)                      # Capacity needed if we exclude ith item
h(i, j) = f(i-1, max(0, j-v(i))) + w(i)  # Capacity needed if we include ith item

```

In the last line, `max(0, j-v(i))` just makes sure that the second argument in the recursive call to `f()` does not go negative in the case where `v(i) > j`.

Memoising this gives a pseudopolynomial O(nc)-time, O(nc)-space algorithm, where n is the number of items and c is the value threshold. You can save space (and possibly time, although not in the asymptotic sense) by calculating it in bottom-up fashion -- this would bring the space complexity down to O(c), since while calculating `f(i, ...)` you only ever need access to `f(i-1, ...)`, so you only need to keep the previous and current "rows" of the DP matrix.
If I understand your question correctly, the problem you wish to solve is on the form:

```
let mass_i be the mass of item i, let vol_i the volume, and let val_i be its value.
Let x_i be a binary variable, where x_i is one if and only if the item is in the knapsack.

minimize (mass_1 * x_1 + ... + mass_n * x_n) //The case where you are minimizing mass
s.t.  mass_1 * x_1 + ... + mass_n * x_n >= MinMass
      vol_1 * x_1 + ... + vol_n * x_n   >= MinVolume
      val_1 * x_1 + ... + val_n * x_n   >= MinValue
      x_i in {0,1} for all i

```

A trick you can use to to make it more "knapsacky" is to substitute `x_i` with `1-y_i`, where `y_i` is 1 one, if and only if item `i` is *not* in the knapsack. Then you get an equivalent problem on the form:

```
let mass_i be the mass of item i, let vol_i the volume, and let val_i be its value.
Let y_i be a binary variable, where y_i is one if and only if the item is NOT in the knapsack.

maximize mass_1 * y_1 + ... + mass_n * y_n) //The case where you are minimizing mass
s.t.  mass_1 * y_1 - ... + mass_n * y_n <= mass_1 + ... + mass_n - MinMass
       vol_1 * y_1 - ... +  vol_n * y_n <= vol_1 + ... + vol_n - MinVolume
       val_1 * y_1 - ... +  val_n * y_n <= val_1 + ... + val_n - MinValue
      y_i in {0,1} for all i

```

which is a knapsack problem with 3 constraints. The solution **y** can easily be transformed into an equivalent solution for your original problem by setting `x_i = 1 - y_i`.