> On Mar 22, 2017, at 8:09 AM, Mark Dilger <hornschnorter@gmail.com> wrote:
>
>
>> On Mar 22, 2017, at 7:55 AM, Andrew Gierth <andrew@tao11.riddles.org.uk> wrote:
>>
>> [snip]
>>
>> This thread seems to have gone quiet - is it time for me to just go
>> ahead and commit the thing anyway? Anyone else want to weigh in?
>
> Sorry for the delay. I'll try to look at this today. Others are most welcome
> to weigh in.
You define DiscreteKnapsack to take integer weights and double values,
and perform the usual Dynamic Programming algorithm to solve. But
the only place you call this, you pass in NULL for the values, indicating
that all the values are equal. I'm confused why in this degenerate case
you bother with the DP at all. Can't you just load the knapsack from
lightest to heaviest after sorting, reducing the runtime complexity to O(nlogn)?
It's been a long day. Sorry if I am missing something obvious.
I'm guessing you intend to extend the code at some later date to have
different values for items. Is that right?
I reapplied your patch and reran the regression tests on my laptop and they
all pass.
mark