01 Knapsack with selection of items with minimum total weight

I have a slightly modified version of a classical 01 knapsack problem. Specifically, the problem has an additional constraint which requires that if more than one feasible selection with equal value exists then the selection with minimum total weight be selected. For example, consider a knapsack with size 3 and the following set of items to choose from; tuple is defined as ("name", weight, value):

items = (("alpha", 3, 4), ("beta", 1, 3), ("gamma", 1, 1))


There exist two possible selections with total weight <= 3 and value = 4:

Selection 1:

[alpha] with a total value of 4 and weight 3


Selection 2:

[beta, gamma] with a total value of 4 and weight 2


Due to the additional constraint, selection 2 is the correct answer. However, the classical 01 knapsack doesn't ensure this. So my question is, does there exist a variant of 01 knapsack which handles this? If not how do I tackle this additional constraint.

So far, I have the following two approaches which can possibly work:

• Calculate the density of the objects and then perform knapsack using density as the value. This approach however is suited to fractional knapsack where any arbitrary amount of an item can be taken. In this case, the item, if taken, must be taken in its entirety.
• Sort the items with respect to weights before running knapsack on them.

1 Answer

Sure. It's easy to take any algorithm to solve the ordinary knapsack problem, and apply it to your problem. In the ordinary knapsack problem, we specify an upper bound on the weight. Once we find the maximum value achievable with that weight, next we'll try to see if we can reduce its weight further. Do this by solving a new version of the knapsack problem, the same as the original, except the maximum weight has been reduced. See how far you can reduce the maximum weight while still achieving the same value. You can use binary search for that.