o-1 Knapsack problem

From: "Radha" <radha.kaipa@xxxxxxxxx>
Date: 20 Feb 2006 19:02:16 -0800

n objects x1...xn, each having weight wi and profit pi, are to be
placed into a sack with capacity M. Can somebody please help me write a
algorithm that determines which objects should be placed in the sack
inorder to maximize the profit.

.

Follow-Ups:
- Re: o-1 Knapsack problem
  - From: Andrey Goder

Prev by Date: Graph Theory and Combinatorics Forum
Next by Date: Solving X3SAT Using Bipartite Graphs
Previous by thread: Graph Theory and Combinatorics Forum
Next by thread: Re: o-1 Knapsack problem
Index(es):
- Date
- Thread

Relevant Pages

Re: The Dont Buy Exxon Gasoline Bit
... company makes as much profit as possible on their product. ... only made a 255 million after tax profit for the last half of 2007, ... BP had a poor year last year. ... Didn't they sack the CEO? ...
(alt.autos.toyota)
Re: OT: Gas Prices -- Help at last?
... > If they are all so costly, then why havent they built new capacity? ... > on the gas than do the oil companies. ... > making a clean 12-20% profit on their product after ALL their expenses. ... Perhaps the government should get into ...
(rec.aviation.piloting)
Re: Weighted Tree
... It needs to find a maximum profit path that is continuous. ... Thing I dont understand is how does this algorithm know that if it takes two siblings it cannot take on any more paths on top of that. ... my tree implementation is that node stores its label and its weight from its parent. ...
(comp.lang.java.help)
Re: Backpacking Kit
... I'm reviewing my backpacking kit and trying to work out whether there's ... a cost-efficient means of reducing the weight. ... the reduced weight than extra comfort. ... I could save 55g by not taking the sack or repair kit. ...
(uk.rec.walking)
Re: [UKSF XI] Gracious concession
... I look forward to working with the new Manager in whatever capacity he ... You're going to wait by the riverbank with a big sack, ...
(uk.sport.football)