Knapsack algorithm optimized for weight instead of values

Question

is it possible to modify the 1-0 Knapsack algorithm to optimize the final total weight of items in the bags as first choice (and the values as second choice), maintaining the same algorithmic complexity?

I'm working on this java implementation (in the end of the article).

More specifically, I'm thinking of changing this piece of code

if (wt[item-1]<=weight){
    V[item][weight]=Math.max (val[item-1]+V[item-1][weight-wt[item-1]], V[item-1][weight]);
}else{
    V[item][weight]=V[item-1][weight];
}

with some other condition that firstly control if the weight is closer to the threshold adding this item and than, if the weight does not change, if the value is better.

Have you got an idea how to do this without change the complexity?

Thank you

EDIT with "firstly control if the weight is closer to the threshold adding this item" i mean reaching the weight limit of the backpack. In other words "maximizing the weight i can carry in my bag" without breaking it

Answer 1

Are you trying to do the following? Choose items so that the weight is maximized, while still respecting the weight limit. If there are multiple optimal solutions that each achieve the maximum possible weight, then choose among them by choosing the solution that has the largest total value.

If so, then I suggest the following. (I'm thinking about knapsack problem itself and not your Java implementation of it.)

Let M = the maximum value [edited] among all the items and N = number of items. Replace each value (in the objective function) with weight + value/MN.

Then the model will maximize the total weight, while still respecting the weight limit. And if there are multiple solutions with the same optimal weight, it will choose the one with maximum value. Dividing by MN ensures that you'll never choose a solution with a better value at the expense of a worse weight.

Answer 2

What does it mean to optimize the final weight? An optimized weight seems to be an empty bag to me.

So yes it would change the complexity to O(1) by making it trivial.

Could you specify your goal?

==EDIT==

Hi, if maximizing your weight at the same time is what you are trying to achieve it seems that we are talking about a dual problem. You could look into linear programming and the dual simplex algorithm (see Wiki)

Answer 3

I finally found a solution specifically to my problem.

i've used the algorithm linked in the question (this) but instead of considering the values of the items i maximize the weight (i've used the weight both as weight and value). So he knapsack algorithm optimizes the weight in the bag, without any consideration for the values.

To maximize the values i've sorted the item in desc order, from greater values to lower, before computing the matrix of the algorithm, and in case of same value (that in my case is he weight) i do not change item composition, because the first items have the greater values so the first set of items has a greater value.

It isn't probably the best solutions but it seems to work good (in my case). Hope could help