Quote Originally Posted by jim enright
example:

the bag can only hold 12 lbs.

you have the following items:

obj wt cost
1 3.8 3.8
2 3.8 3.8
3 3.8 3.8
4 3.0 2.9
5 3.0 2.9
6 3.0 2.9
7 3.0 2.9

the optimal solution is to pick the four lowest lowest cost and lowest cost
per lb objects. the example is contrived but the point is that this is
a difficult optimization problem that can only be solved by
sophisitcated integer programming techniques or sheer exhaustion
of the possibilites. strategies often work well but do not guarantee true "optimization".

dynamic programming relates to a series of sequential decisions through time or stages and typically is more of an art than an algorithm. but
integer programming can be classified as DP.

this greedy algorithm that you state can be an effective solution, but it is NOT the solution to this problem. for instance
say you have 4 items for a 4 lb sack:
obj lbs $$
1. 3 14
2. 2 8
3. 2 8
4. 1 1

you solution would have the person pick the 3 lb item and then the 1 because the 3 has highest value and 1 will fit.
the proper solution is to pick the two 2lb items.

the solution is to do the following:

lbs take? price take? price Take? price take? price
4 x 14 14 x 16 16
3 x 14 14 14 14
2 0 x 8 8 8
1 0 0 0 1
3lb item 2lb item1 2lb item2 1lb item

you look at the items 1 at a time, I probably should have started with the lightest, but hey what you gonna do. anywho you then add an item by comparing it to each weight ( to add the second 2lb item you look and say hey this item weighs 2 lbs. If i ad this to the other current load at 2lbs my total 4lb value would be higher so i think i should take this one).

tex23bm