2
$\begingroup$

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.
$\endgroup$
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.