3 ms·
This is a "false" solution, in the sense that you can create a large number of scenarios where just taking the most value/weight efficient item, regardless of t
by crazypyro 12y ago
This is a "false" solution, in the sense that you can create a large number of scenarios where just taking the most value/weight efficient item, regardless of the relationship between the items, will result in a non-optimal solution.
e.g. 2 Silver coins worth 4 and weighs 2. 1 Gold coin worth 5 and weighs 3. Silver slightly more efficient, but if your bag size is 5, the obvious solution is 1 gold + 1 silver coin worth 9, where as your "algorithm" would give 2 silver coins weighing 8, worth 8.
- hayksaakian 12y agoI guess my solution was more approximate but easier to reason about. You're right, it falls apart on the borders of max capacity.