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:
[alpha] with a total value of 4 and weight 3
[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.