2 ms·
The 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
by thaumasiotes 7y ago
The 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.