Hacker News Reader

Comment by SOTGO | Hacker News Reader

I get that the author wanted to explore constraint solvers, but why can't you use a greedy algorithm for this problem? Sort the inventory slots by how much bundle space they consume, and insert the cheapest slots. The only way I see this failing is with multiple bundles, but in practice in Minecraft (which is admittedly not really part of the constraint problem) bundles only help when you have many distinct items but a large number of items occur only a few items. In that case it isn't hard to find combinations that fill each bundle completely by only inserting all of a given item (as opposed to inserting only part of an inventory slot) since many items will have only 1 or 2 copies.

View on HN

I opt for the greedy strategy in most game play scenarios for pretty much the reasons you described here. I was considering making a mod to perform this action for me and was looking for a more "correct" solution but greedy is way simpler and just as effective for most cases.

If you greedily fill bundles by first inserting all weight-4 items (pearls, etc.) in any order into a single bundle, moving to a new bundle each time the current one gets full, then inserting all weight-1 items (sticks, etc.) in any order in the same way, the solution you get will use an optimal number of bundles, and also leave an optimal amount of free capacity in the final bundle. (It helps to notice that every bundle except the last must be completely full with no wasted space, since both 4 and 1 divide 64.)

If you do the same, but add all weight-1 items before adding all weight-4 items, you'll still get a solution using the same (optimal) number of bundles, but you may use more capacity in the final bundle than needed -- e.g., if you have 61 sticks and 1 pearl, and add them in that order, the first bundle wastes 3 slots and the second uses 4 slots (vs. no wasted space in the first bundle and just 1 slot used in the second if adding in the reverse order).

OTOH, if you mix adding items of different weights (while staying with the approach of only ever adding to the current bundle if there's room, and if not, moving to a fresh bundle) then you can arrive at a suboptimal number of bundles. E.g., adding 61 sticks, 1 pearl and 3 dirt in that order will require 3 bundles instead of the optimal 2.

Reply on news.ycombinator.com