Reputation: 53
I'm trying to solve the following problem:
I have a set of N
items, where each pair of items have a mutual score, and I need to select a combination of W
items such that the overall score is the greatest.
The overall score of items i,j,k
for example is
score(i,j) + score(i,k) + score(j,k).
In order to avoid going through all N^W
possible combinations, I thought about doing a variation on the 0-1
knapsack problem and solve with dynamic programing with these 2 changes:
W
items in my sack) I already started coding the solution with these two changes, however now that I think about it more I'm afraid that it can't be solved with dynamic programing since the "optimal substructure" property doesn't hold.
For instance, if W=3
and items i,j,k
is the optimal solution, then for W=2
, i,j
is not necessarily an optimal solution (according to the calculation of overall score above).
Does anybody have an idea how this problem can be solved with dynamic programing and not with O(N^W)
brute force?
Thanks
Upvotes: 1
Views: 1353
Reputation: 4661
Your problem is NP-hard, which means there is almost certainly no fast polynomial time algorithm to solve it, because no one has been able to come up with a polynomial time algorithm to solve an NP-hard problem. To see NP-hardness, suppose you have a graph where nodes are your indices and you define the score between i,j to be 1 if there is an edge between i and j, otherwise 0. Then if you can, in polynomial time, find the maximum score subset of nodes that have at most W nodes included, then you can, in polynomial time, figure out if there is a clique of size W in your graph. This is an NP-complete problem.
Upvotes: 1