lootsack
lootsack is a small C suite that frames the classic 0/1 knapsack problem as a treasure-hauling dilemma: given a pile of randomly generated loot — coins, crowns, daggers, gems, necklaces, rings, swords — and a maximum weight an adventurer can carry, pick the subset that maximizes total gold-piece value.
Goals
- Provide a self-contained sandbox for experimenting with knapsack solution strategies on realistic-looking treasure data.
- Stay portable to BSD systems — the build uses
bsd.prog.mk, and the generator drops privileges withpledge(2)andunveil(2). - Keep the data format simple and stable: a versioned binary file for fast loading, plus a CSV format for inspection and editing.
- Grow the problem over time with optional complications — unknown weights, appraisal skill, time pressure, pack volume — that turn a textbook exercise into something more game-like.
Programs
lootsack— read a binary treasure file and pick a haul under a given max weight. Currently uses a greedy value-to-weight selection.lootsack-generate— produce a randomized pile of treasure in either binary or CSV form.lootsack-display— print the contents of a binary treasure file in human-readable form, or summary stats with-s.lootsack-bin-to-csvandlootsack-csv-to-bin— convert between the on-disk formats.
How it works
Treasure types have per-type weight and value ranges
(lootsack.c) and a
sampling frequency that makes coins common and swords rare. The
generator (generate.c)
uses arc4random_uniform to draw a type and then random
weight/value within that type's bounds. The selection routine in
main.c sorts by a fixed-point
value-per-weight ratio and greedily takes items that still fit
— a fast approximation, not an optimal solver. A heap-based
and a true dynamic-programming solver are tracked as future work in
the README.