Beefy Boxes and Bandwidth Generously Provided by pair Networks
laziness, impatience, and hubris

Re: Solution for Knapsack

by batkins (Chaplain)
on Jan 24, 2004 at 22:39 UTC ( #323883=note: print w/replies, xml ) Need Help??

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
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.

Log In?

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://323883]
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others meditating upon the Monastery: (3)
As of 2022-12-10 06:12 GMT
Find Nodes?
    Voting Booth?

    No recent polls found