Bài toán cổ điển: cái túi

Cái túi

Cho N đồ vật , vật i có khối lượng W[i] và giá trị là V[i] . Một cái túi có thể chịu được khối lượng tối đa là M , quá thì sẽ rách. Hãy tìm cách nhét 1 số đồ vật vào trong túi sao cho túi không bị rách và tổng giá trị của các đồ vật nhét vào là lớn nhất.

Phải có bộ test chứ? cho đề ko thế này biết đường nào làm?

hoangtin14 đã viết:

Phải có bộ test chứ? cho đề ko thế này biết đường nào làm?

Bộ test nào cơ chứ. Thì bạn cứ nêu suy nghĩ đi đã ^^.

code:

var n,m:longword;
f:array[0..500, 0..500] of longword;
w,v:array[0..500] of longword;
i,j:longword;
begin
read(n,m);
for i:=1 to n do
read(w[i], v[i]);
fillchar(f[0], sizeof(f[0]),0);
for i:=1 to n do
for j:=0 to m do
begin
f[i,j]:=f[i-1,j];
if (j>=w[i]) and (f[i,j]<f[i-1, j-w[i]] + v[i]) then
f[i,j]:=f[i-1, j-w[i]] + v[i];
end;
writeln(f[n,m]);
readln
end.

Bạn quy hoạch động dùng mảng 2 chiều à, cũng được, bị cái hơi phí nhưng dễ cài và truy vết. Mà code của bạn chưa có truy vết thì sao in kết quả. Chỉ in n và m thì ko hay

toan_9a2 cùng trường với lit à. mấy hôm nay ôn thi chuyển cấp bận quá ko lên dc. hôm nay lên thấy bàn luận sôi nổi ghê ^^

Ko đâu. toan_9a2 với tớ chả quen biết gì cả^^ . Thì Tín để ý mà xem, trường tớ xếp khối 9 theo thứ tự mà (1,2,3....). Còn trường của bạn toan_9a2 có cả các kí tự a,b,c vô nữa ^^

Mấy hum ni tớ cũng bận ôn thi chuyển cấp

trường mình cũng có a,b,c.