4 ms·
Ask HN: RPG Inventory Sorting Algorithm?
Dear HN crowd.
I'm currently learning about algorithms, and I decided to think of a problem I encounter that I would like to solve. One such problem is when games (often RPGs) have a 'Tetris' style inventory system, with items of different shapes and sizes.
I have decided I would like to make a sorter for game I play, to help me quickly maximise my storage space.
However, after a preliminary google, I didn't find much in the way of resources for problems like this, so I assume my google-fu is weak.
Would anyone know of any examples, or preferably, underlying math/code to help me grasp this?
Thank you in advance!
- h2odragon 4y agohttps://en.wikipedia.org/wiki/Knapsack_problem https://en.wikipedia.org/wiki/Knapsack_problem much room for a cool game there; good luck!
- bloqs 4y agoThis is exactly what I was after thank you!
- verdverm 4y agoYou might start with a greedy solution, i.e. take the biggest items first. Then explore other options as your google-fu hones in on good search terms for the problem. Bin packing is a good search tree to go down, but you have a layout problem as well. The Algorithm Design Manual as a large index of problems and algos that can help in finding analogies to your given problem.
- compressedgas 4y agoPolyomino packing is solved by Set cover.