Re: rosettacode 500 milestone passed
- Posted by Spock Mar 19, 2017
- 1574 views
I translated the C dynamic programming version:
...
Simple and elegant, yet quite difficult to get your head around - there are some youtube vids (search for knapsack problem) that might help.
Pete
Nice. There are a constant 14k total internal iterations in the main loops, regardless of input order. Unrolling the data to unit size only slightly increased the loop count. I tried various pre-sorting modes but only got modest improvements on the inner if blocks. So, all up very well crafted.
I note the CPP version is described as "Initially taken from C but than fixed and refactored". Does that mean some subtle bug still lurks in the C version? The CPP version is also 3 times longer than the one in C. I didn't realise that "refactor" actually means to make longer.
Spock