Permalink Submitted by Daniel Flatow on April 21, 2017

Convert it to a linear programing problem to be solved using the simplex method.

Let there be a variable for every present, and constrain every variable to lie between 0 (do not pack) and 1 (do pack). The weight limit is another linear constraint, and the total value of presents packed is the linear objective function.

Granted that the optimal solution may (and probably will) involve a fractional number for various presents, and you may ask, "how can I pack 2/5 of a given present, when I can only either pack the whole thing or not pack any of it?" Well, the next step is to transform the whole space, including you fractional optimal solution, so that the hyperplane (flat space of one fewer dimensions than the number of presents) that corresponds to the optimal level (which contains your optimal solution point) contains all of the transformed coordinate axes except for the last one, and what were the feasible integer vertices (that corresponded, for every present, to either packing it or not packing it, and that did not cause the total allowable weight to be exceeded) are transformed to points on one side of that hyperplane, and have a positive last coordinate, and the non-feasible integer vertices are transformed to the other side, and have a negative last coordinate. Then the true integral optimal solution will be integer vertice that was transformed to the point with the minimum positive coordinate.

## solution

Convert it to a linear programing problem to be solved using the simplex method.

Let there be a variable for every present, and constrain every variable to lie between 0 (do not pack) and 1 (do pack). The weight limit is another linear constraint, and the total value of presents packed is the linear objective function.

Granted that the optimal solution may (and probably will) involve a fractional number for various presents, and you may ask, "how can I pack 2/5 of a given present, when I can only either pack the whole thing or not pack any of it?" Well, the next step is to transform the whole space, including you fractional optimal solution, so that the hyperplane (flat space of one fewer dimensions than the number of presents) that corresponds to the optimal level (which contains your optimal solution point) contains all of the transformed coordinate axes except for the last one, and what were the feasible integer vertices (that corresponded, for every present, to either packing it or not packing it, and that did not cause the total allowable weight to be exceeded) are transformed to points on one side of that hyperplane, and have a positive last coordinate, and the non-feasible integer vertices are transformed to the other side, and have a negative last coordinate. Then the true integral optimal solution will be integer vertice that was transformed to the point with the minimum positive coordinate.