need help...

Quote:

---

Originally Posted by ppl1

someone...?help?

---

ha ha ha, oh sorry that was inappropriate.

what you do is find a standard for all your weight. so say each item is rounded to the pund and you can store five pounds.
you keep track of how much value can be stored in a 1 lb sack an 2 lb sack a 3 lb... to 5 lbs. now, you add each item 1 at a time. you look at the previous results and ask. could i increase the value of this element by adding it?
Ex: take the 5 lb bag. you currently have have 5lbs of items worth $4. you also have 2lbs of items worth $2. you are looking at a 3lb item worth $3. you would add this item because if you combined that item with the items in the 2lb sack you get $5 instead of $4. this is why you keep track of the all the earlier possible weights.

If you need a better explanation I can give you a much more detailed example, just e-mail me or private message me.

tex23bm.

PS i'm thinking of putting something about this problem on my site for future ref.

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