0/1 Knapsack problem with overlapping items 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?
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 &amp; 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 }