響きの声

So this morning the first years taking ENGGEN 131 handed in their solutions for a simplified knapsack problem. The story goes like this:

You have some number of boxes of a predetermined size, along with some number of weights, each with its own specific weight value. Your job is to find the best possible packing for the weights into the boxes so that you have a minimum number of unused weights.

I don’t have to take ENGGEN 131, but I decided to take a shot at it anyway.

After several miserable failures with ideas such as packing the boxes one at a time, I arrived at my semi brute force solution involving three (and a half) simple optimisations which can cut the number of combinations to test by quite a large number (eg. 4 billion combinations cut to around 300k).

Source: knapsack.c
Explanation: knapsack.txt

edit:

Also you can flip single line /* */ style comments to // comments while preserving whitespace at the front of the line using VS regex find and replace. Search

^{.*}/\*{.*}\*/.*$

and replace with

\1//\2