Printable View
hello,
i have items with cost and weight and i need to put them in a box (that has a capacity of weight) so that the cost of all the items in it will be the higher as possible.
now what i know is that the higher cost of the item---> the weight is low
can you help me with finding an algorithm?
thanks
it's a well-know problem, knapsack problem. You can search for information about it in the Goooogle.
Yes, this really is a well known knapsack problem. I know it as "the bag problem". Let say that the box has capacity equal to M and you have N objects to put in it. Each object has its capacity Ci and value Vi. To solve it you need a to dimensional array A[1..N][1..M]. And for each integer i from 1 to N and for each integer j from 1 to M:
A[i][j] = max(a[i][j - 1], Vi + a[i - 1][j - Ci])
and here is the sors written in pascal:
type el = record
V, C : longint;
end;
const ogr_m = 50;
const ogr_n = 50;
const beyond = 2000000000;
var a : array[0..ogr_n, 0..ogr_m] of longint;
b : array[1..ogr_n] of el;
i, j, k, l, o, p, m, n : longint;
v1, v2, v : longint;
function max(k1, k2 : longint) : longint;
begin
if k1 > k2 then max := k1
else max := k2;
end;
begin
readln(n, m);
for i := 1 to n do
readln(b[i].C, b[i].V);
for j := 1 to m do
if j >= b[1].c then
a[1, j] := b[1].v;
for i := 2 to n do
for j := 1 to m do
begin
v1 := -beyond;
v2 := -beyond;
v1 := a[i - 1, j];
if j - b[i].c >= 0 then v2 := b[i].v + a[i - 1, j - b[i].c];
a[i, j] := max(v1, v2);
end;
writeln(a[n, m]);
end.
Its 1am in Bulgaria so that is not one of my best sorses. If you want it in C++ or any othe language just tell me.
yes but here it is known that the higher cost of the item---> the weight is low
so how to get help from that?
thanks for the help
Say, there is an item with greater cost out of the pack then the one in the pack. According to your condition, its weight is lower. So you can place it instead of that in the pack (it would fit as its weight is lower), and it would improve the pack, as its cost is higher.
The same can be applied to item with the same cost, but lower weight.
Now you can formulate explicit rule of filling the pack (without replace iterations).
in each iteration im checking if an item is suitable (im checking his weight + if he is improving the cost) and if he is ok then im putting him into the sack,
but thats exactly that the general knapsack algorithm is doing !
do whats the difference (in the algorithm)?
it seems to me that the general algorithm is the same to my problem...
thanks
Just think a little about what I wrote in that post. You can write explicit solution without any iterations.Quote:
Originally Posted by RoboTact
you mean to use the greedy algorithm?
to put first all the items with the lowest weight?
someone...?help?
this is an integer programming problem whose general solution is
complex. for small numbers of items you can use an exhaustive
search through all combos of the items.
say you have n+1 items, each with a cost, c[i], and weight, w[i].
set up an inclusion var i[i] = 1 if included, 0 if not
maxcost = 0;
for (i[0] = 0; i[0] < 2; i[0]++){
for (i[1] = 0; i[1] < 2; i[1]++){
....
for (i[n] = 0; i[n] < 2; i[n]++){
totalweight = i[0]*w[0] + i[1]*w[1] ...
totalcost = i[0]*c[0] + i[1]*c[1] ...
if totalweight < allowedwt {
if totalcost > maxcost {
maxcost = totalcost
{save your i[i]!}
}
}
....
}
at the end you will have the saved i[i] telling you which itesm to inlcude
sorry for the probable lack of indentation - dont know how to use code tags
thanks but the truth is that i dont know "integer programming"
is there a solution to that problem in dynamic programming?
thanks for the help
No, no - problem is very simple...
As I already written, the pack is only improved when you places items with most cost (first) and less weight (second) in the pack, and that you always can do it if there is an item out of the pack with bigger cost (hence also with lower weight) or with lower weight. So you can put in the pack items with maximum cost from the start, and of all items with lower cost put in the pack select items with lower weight.
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.
Yes, correct, but the assignment:Quote:
Originally Posted by ppl1
ok thanks for the help!!!