1

From wiki:

Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible

Given that all items costs are 1$ for 1Kg, aka weights are equal to values. Will this problem will also be NP-hard like knapSack 0-1?

Ilya Gazman
  • 1,440
  • Consider the subset sum problem. – Brian Borchers Jul 20 '20 at 13:30
  • @BrianBorchers the answer to the subset sum problem is boolean, how can you turn it into finding the smallest value above 0? – Ilya Gazman Jul 20 '20 at 13:55
  • The subset sum is also NP complete, not NP hard. Can you find a way to make an NP hard variation on the subset sum problem that is entirely equivalent to your problem? Or maybe change your problem into a decision problem which can then be seen as a rewrite of the subset sum problem? – Arthur Jul 20 '20 at 14:58

0 Answers0