http://qs321.pair.com?node_id=323883


in reply to Solution for Knapsack

I haven't tried to grok your code yet, but your title makes me highly skeptical. The knapsack problem is NP-hard, meaning that if you truly have found a way to do it in polynomial time, then all other NP-hard problems can also be done in polynomial time. That would be quite a breakthrough.
Are you sure it was a book? Are you sure it wasn't.....nothing?

Replies are listed 'Best First'.
Re: Re: Solution for Knapsack
by stu96art (Scribe) on Jan 24, 2004 at 23:11 UTC
    I apologize, I did not mean to say that I solved the knapsack problem. I have written code that executes a branch and bound method of solving a version of the knapsack problem. I was hoping that it would get looked at and possibly some suggestions could be given on making it faster. Thanks, again
[reply]
Re: Re: Solution for Knapsack
by stu96art (Scribe) on Jan 29, 2004 at 20:07 UTC
    I have code that tries to eliminate iterations by climbing back up the tree if $waste=$bestwaste more than ten times in a row. I am afraid that I could miss out on a solution, but I did not know where else to turn. If anyone has any ideas or opinions, would you please let me know. Thanks ya'll.
    Read more... (24 kB)
[reply]
[d/l]

In Section Seekers of Perl Wisdom