0
$\begingroup$

Here's a doozy:

Given a knapsack with a capacity W, and n overlapping items (definition of overlapping to follow), which items should we take to maximize the value of the knapsack?

In this problem, you can think of an "item" as a bag of coins with the following properties:

  • There are many, many different types of coins (1M+)
  • Every coin is worth the same amount
  • Each bag has at most one of any type of coin

For example, bag 1 might have two coins, one of type A and another of type B. And bag 2 might have two coins, one type B and one type C.

We can only take one of each type of coin. So picking bag 1 and bag 2 would mean that we have 3 total coins (one A, one B, and one C).

How can we figure out which bags to take to maximize the number of coins you can take?

The subproblems aren't independent, so I don't think we can use dynamic programming.

For extra credit:

How can we get within a certain threshold, say 10%, of the capacity W as fast as possible?

Improve this question
$\endgroup$
8
  • $\begingroup$ just to clarify: so you can't take both bags A and B, is it? And what are the weights of the different types of coins? $\endgroup$
    – Mathguy
    Commented Jun 4, 2016 at 0:33
  • $\begingroup$ What role does the capacity play? $\endgroup$
    – user555045
    Commented Jun 4, 2016 at 1:12
  • $\begingroup$ @Mathguy Great questions. I clarified the question to say that while you can take bag 1 and bag 2, if you do, you have to get rid of any duplicate coins. The weights of every type of coin is the same, so we can act as though they all have a weight of 1. $\endgroup$
    – yndolok
    Commented Jun 4, 2016 at 4:52
  • $\begingroup$ @harold Thanks for the question. The capacity of the knapsack is essentially the number of coins you can take. $\endgroup$
    – yndolok
    Commented Jun 4, 2016 at 4:53
  • $\begingroup$ Do we "get rid of any duplicate coins" before or after calculating the total weight? ​ ​ $\endgroup$
    – user12859
    Commented Jun 4, 2016 at 8:27

1 Answer 1

Reset to default
1
$\begingroup$

Calling this a variant of Knapsack is a bit confusing, since it's more like maximum-weight independent set. Bags are nodes, bags that share a type of coin have an edge between them, and the number of coins in each bag is the weight of the node. Going the other way is annoying, translating unweighted MIS into this problem is easy though.

Anyway here's a direct ILP formulation of the coins/bags thing:

maximize sum of take_bag[i] * size[i]
s.t.
∀c: sum[i | c ∈ bag[i]] of take_bag[i] ≤ 1
take_bag[i] ∈ { 0, 1 }

You could use the linear relaxation of that to do branch & bound, which you can stop early when you're happy enough with the gap between the best found solution and the objective value of the linear relaxation. Or check the literature for MWIS solving. There are many approximation algorithms as well.

Taking into account the capacity constraint, the ILP model becomes

maximize sum of take_bag[i] * size[i]
s.t.
∀c: sum[i | c ∈ bag[i]] of take_bag[i] ≤ 1
sum of take_bag[i] * size[i] ≤ W
take_bag[i] ∈ { 0, 1 }
Improve this answer
$\endgroup$
5
  • $\begingroup$ Please correct me if I'm wrong - I don't think this algorithm takes the maximum total weight (capacity) into account. That's why I thought this was a variant of the knapsack problem - we can't take more than W coins. $\endgroup$
    – yndolok
    Commented Jun 4, 2016 at 21:55
  • $\begingroup$ @yndolok so it is a constraint after all. No problem for ILP, but that makes this "not MWIS" $\endgroup$
    – user555045
    Commented Jun 4, 2016 at 21:57
  • $\begingroup$ Yes, it is a constraint. Sorry for the confusion. How could we modify the ILP formulation you gave to take the capacity into account? $\endgroup$
    – yndolok
    Commented Jun 4, 2016 at 22:01
  • $\begingroup$ Is the ILP solution essentially the equivalent of trying every possible combination of bags until we find a combination of bags with a capacity W? And if we've tried every combination, and none have a capacity of W, we just return the largest combo of bags with a sum < W? $\endgroup$
    – yndolok
    Commented Jun 5, 2016 at 2:15
  • $\begingroup$ @yndolok the result is equivalent (not necessarily the same due to the order of solutions with the same objective) but IMO that does not make it equivalent as a solution - the whole point of having that model is so it doesn't have to try every combination because it can prune large parts of the search space. $\endgroup$
    – user555045
    Commented Jun 5, 2016 at 9:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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