Re: rosettacode 500 milestone passed
- Posted by Spock Mar 15, 2017
- 1850 views
Just tooting my own horn, Phix on rosettacode has recently passed the 500 milestone.
I have also found an interesting possible optimisation for the Knapsack/Bounded problem, and invite anyone to join in the discussion (on that page or here):
At first glance I think I would make it easy on myself by reforming the data a bit:
- Expanded 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
(You do 2 of these 3 things)
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.
In a quick test I noticed that just sorting the raw (unified) data by a weighted score column almost produced the optimal result on its own.
Spock
