OpenEuphoria

In the Phix solution, I noticed the order of goodies had an impact on search time, ranging from 12s (highest value/fewest items first) to 28s (lowest value first), which got me thinking. I also noticed that sometimes the optimal solution was found very early, and came up with a little theorem.

If we sort by weighted value, and on the last item (given that we have been greedy) we can take the full complement, I believe that means we must be on or have passed through the optimal solution.

Since I am not entirely convinced that hypothesis is right (it does seem rather unlikely that no-one has ever thought of it before), I have left the Phix solution such that it completes the full scan and crashes if a disproving dataset is used. One thing I have tried is increasing the available beer: at 8 and above it never displays "terminate" (it is the last item and 8 will not fit) and must perform a full search, which I view as a good sign, even though it means there is no gain in such circumstances. Actually, there is another possible optimisation right there: 7 beer will terminate in 1.49s (vs 15.3s for 8) so cap the last entry, after sorting, at something that will fit[now added]. It is also interesting to note that we can terminate even if the selection being inspected has not improved matters. Pete Lomax (talk) 13:58, 15 March 2017 (UTC)