I submitted a comment on how this problem could be solved as a linear programming problem, using the simplex method. Every present could be a variable, ranging from 0 (don't pack) to 1 (do pack), that the weight limit could be an additional constraint, and that the total value could be the objective function to maximize.
The optimal solution would likely involve fractional values for every present variable, and only integer solutions (0 or 1) are possible, and I added that the entire space could be essentially rotated (and translated) so that the hyperplane containing the optimal value is transformed to the hyperplane with the equation that the last coordinate is 0, and all of the integral feasible points that met the total weight constraint would be mapped to points with the last coordinate positive. Then I said that of all the images under the rotation/translation of the integral feasible points, the optimal integer solution would correspond to the image point with the lowest positive value for the last coordinate.
Well, I confused the hyperplane of the optimal total value with the hyperplane of the maximum possible weight. So I accordingly modify my algorithm. Instead of the rotation/translation, use a linear (or affine) transformation that maps the hyperplane of the optimal value to that with the equation that the last coordinate is 0, and that also maps the hyperplane of the maximum allowable weight to the hyperplane with the equation that the second last coordinate is 0, and such that a positive last coordinate indicates the total value is less than the optimal and a negative last coordinate indicates the total value is greater than the optimal, and such that a positive second last coordinate indicates an allowable total weight, and finally such that the absolute value of the last coordinate is the difference between the total value and the optimal value (there is at least one such transformation such that all this is possible).
Finally, of all the images under the linear/affine transformation of the integral feasible points, the optimal integer solution will be the one with the positive second last coordinate and the minimum positive last coordinate.
I submitted a comment on how this problem could be solved as a linear programming problem, using the simplex method. Every present could be a variable, ranging from 0 (don't pack) to 1 (do pack), that the weight limit could be an additional constraint, and that the total value could be the objective function to maximize.
The optimal solution would likely involve fractional values for every present variable, and only integer solutions (0 or 1) are possible, and I added that the entire space could be essentially rotated (and translated) so that the hyperplane containing the optimal value is transformed to the hyperplane with the equation that the last coordinate is 0, and all of the integral feasible points that met the total weight constraint would be mapped to points with the last coordinate positive. Then I said that of all the images under the rotation/translation of the integral feasible points, the optimal integer solution would correspond to the image point with the lowest positive value for the last coordinate.
Well, I confused the hyperplane of the optimal total value with the hyperplane of the maximum possible weight. So I accordingly modify my algorithm. Instead of the rotation/translation, use a linear (or affine) transformation that maps the hyperplane of the optimal value to that with the equation that the last coordinate is 0, and that also maps the hyperplane of the maximum allowable weight to the hyperplane with the equation that the second last coordinate is 0, and such that a positive last coordinate indicates the total value is less than the optimal and a negative last coordinate indicates the total value is greater than the optimal, and such that a positive second last coordinate indicates an allowable total weight, and finally such that the absolute value of the last coordinate is the difference between the total value and the optimal value (there is at least one such transformation such that all this is possible).
Finally, of all the images under the linear/affine transformation of the integral feasible points, the optimal integer solution will be the one with the positive second last coordinate and the minimum positive last coordinate.