4 ms·
Interesting problem. If you play a game like elder scrolls skyrim or oblivion, you run into this problem literally. Without reading, I already knew the solutio
by hayksaakian 12y ago
Interesting problem. If you play a game like elder scrolls skyrim or oblivion, you run into this problem literally.
Without reading, I already knew the solution.
To solve it in your head: sort items by most value/weight efficient to least efficient.
Then take as much as you can until you're full.
(in a game like elder scrolls oblivion, that means jewelry first, and silver vases last)
-----
edit: I am mistaken, as some of the below comments accurately pointed out.
- crazypyro 12y agoThis 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.
- shliachtx 12y agoThat's not necessarily the case. For example: If you have 10[s] (units of space) in your knapsack, and you have 3 items in front of you the first with two with 5[s] and 4[v] (units of value) each, and the third with 6[s] and 7[v], the best solution would be to take the first two, even though they have a lower [s]/[v] ratio, because you will end up with 1[v] more.
- hayksaakian 12y agoyou are correct, i was mistaken.
- ekr 12y agoThat's the greedy(and obvious) solution, which is optimal for the fractional version of the problem, not in the case of the 0/1 problem, mentioned in the article. If you want a really challenging problem, look into the multiple knapsack problem.