4 ms·
I've always thought of it as "the Skyrim problem", since it's precisely what you do in any RPG with tons of loot and finite carrying capacity My mental algorit
by _bxg1 7y ago
I've always thought of it as "the Skyrim problem", since it's precisely what you do in any RPG with tons of loot and finite carrying capacity
My mental algorithm is:
1) Set a value/weight ratio above which new items are picked up
2) If I run out of space and find something above that threshold, start dropping the worst-ratio'd items to make room
3) Raise the threshold accordingly
4) Repeat
- dahfizz 7y agoWhile 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.
- irjustin 7y agoIf we're trying to reveal when we first really encountered and devoted serious thought (and by association, our age)... I would call this the "Diablo I" problem.
- Jach 7y agoNever thought to equate the two problems.. My algorithm has been: play until I get sick of the nonsensical inventory-management minigame (https://i.pinimg.com/originals/14/f1/e8/14f1e8a75445df681e72d5e3e80284f4.jpg https://i.pinimg.com/originals/14/f1/e8/14f1e8a75445df681e72...) and then running player.setav CarryWeight 1500. Sometimes the solution is to acquire a bigger knapsack.
- vsareto 7y agoI don't think they're similar since knapsack has to consider volume/weight/value in practical applications. Value/weight is only two dimensions.