Re: rosettacode 500 milestone passed
- Posted by Spock Mar 16, 2017
- 1757 views
.. I would make it easy on myself by reforming the data a bit:
- Expand the data set to unit size
- replace pieces field with a weighted score, v/w or something like that
- Sort data by that score column before starting
Next I would split the data into 2 sorted lists - a good one and a bad one. The good one would be my best choices and the bad one is all the rest (with Beer right at the very end). The algorithm would essentially be bubble sort with a twist. I would take the top 2 elements of the bad list and see if they can be swapped them with one element in the good list if that would give me a higher total whilst still keeping the good list under 4kg. Algorithm ends if the scan of the good list reaches the end without being able to swap.
Well, that's my best guess. Can't say how [in]elegant it might be - or even correct.
This first idea didn't find an optimal solution. But thanks to a hint in Pete's later post a single swap scan was added just before the double swap scan. Also, both lists left unsorted (except for the initialisation sort). Now the algorithm seems to give the correct answer in both examples. Stats:
400 kg example
- Time 0.016s
- Total element compares 4525
- Top level iterations 3 (or 6)
10kg example
- Total element compares 7
Spock
