Is this NP-Hard or is there a known optimal polynomial time solution?
Let's say we have 10 items, each with a different cost
Items: {1,2,3,4,5,6,7,8,9,10}
Cost: {2,5,1,1,5,1,1,3,4,10}
and 3 clients
{A, B, C}.
Each client has a requirement for a set of items. He will either buy all of the items in the set or nothing. There is only one copy of each item. For example, if
A requires {1,2,4}, Total Money Earned = 2 + 5 + 1 = 8
B requires {2,5,10,3}, Total Money Earned = 5 + 5 + 10 + 1 = 21
C requires {3,6,7,8,9}, Total Money Earned = 1 + 1 + 1 + 3 + 4 = 10
So, if we sell A his items, B won't buy from us because we no longer have item 2 with us. We want to make the most money. By selling B, we cannot sell A and C. So, if we sell A and C, we make 18. But only by selling B, we earn more, which is 21.
We thought of a bitmasking solution that is exponential in order, although only possible for a small set of elements. And other heuristic solutions that gave us sub-optimal answers. But after several attempts, we couldn't find the optimal solution.
We were wondering if this is a known issue or similar to any issue? Or is this NP Hard problem and therefore the polynomial optimal solution doesn't exist and we're trying to achieve something impossible?
Also, is there a problem if all items are the same?
Many thanks.
source to share
This is a (weighted) packaging problem , one of the original NP-Karp 21 problems. The unweighted version is also NP-hard. If you are trying to solve it efficiently in practice, a sane approach is to feed the following integer program (from Wikipedia) into the solver. Let it be x_i = 1
if we satisfy the client i
and x_i = 0
if we do not satisfy the client i
.
maximize sum_{customers i} (profit from selling to i) * x_i
subject to
for all items j, sum_{customers i desiring j} x_i <= 1
for all customers i, x_i in {0, 1}
source to share