New answers tagged

0 votes

Variant of the Knapsack Problem 0-1 - One item from each set and zero-weighted items

If I have realized the problem, I think this problem is more similar to matching problem than knapsack problem. In other words, you can introduce a bipartite graph with two sets $S$ of objects (A, B, ...
user avatar
0 votes

Variant of the Knapsack Problem 0-1 - One item from each set and zero-weighted items

If weights aren't too large, use the standard pseudo-polynomial-time algorithm (using dynamic programming) for the knapsack problem. It is easy to adjust to this setting. See https://en.wikipedia....
user avatar
  • 141k

Top 50 recent answers are included