3 ms·
While this is usually a decent approximation, it's important to note this is not an optimal solution. For example: Your bag can hold 10 kg. Item a weighs 10kg
by dahfizz 7y ago
While this is usually a decent approximation, it's important to note this is not an optimal solution. For example:
Your bag can hold 10 kg. Item a weighs 10kg and is worth $10. Item b weighs 5kg and is worth $6.
Item b is more value dense, but picking up item a is optimal.
- _bxg1 7y agoYeah, it's just a heuristic
- mjevans 7y agoThis is true, but in the Skyrim case nearly all items are small enough that a 'near optimal' answer is the indicated algorithm, with that extra space a more literal 'garbage collection' free zone. In videogames, making the user GC isn't fun, and therefore reducing the number of GCs is more optimal than strictly solving the problem.
- thaumasiotes 7y agoThe counterexample is not apt; you can see by the phrasing of the original algorithm that items arrive in a stream over time. The goal is to maximize the value of the knapsack once the entire stream (of indefinite length) is consumed. Item B is better than item A, even when you're just choosing from those two items, because more items will come along later to fill the space that item B leaves empty. Here's a more explicit description of the problem space: - Items arrive in a stream. - Picking up an item is free. - Overlooking an item is free. - Discarding an item is expensive. - Once an item is overlooked or discarded, it can't be picked back up. What you're trying to do is finish the stream with the most valuable knapsack without having to go through too much discarding. An item that fills your entire inventory can never be worth picking up, unless it has an awesome value/space ratio, because picking up any other item guarantees that you have to discard that one.