Diễn đàn tin học Nguyễn Văn Linh

The second house for every one
 
IndexTrợ giúpTìm kiếmThành viênĐăng kýĐăng Nhập

Share | 
 

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

Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down 
Tác giảThông điệp
littlelee
Admin
Admin


Tổng số bài gửi : 415
Join date : 20/12/2009
Age : 21
Đến từ : Nghĩa địa

Bài gửiTiêu đề: Bài toán cổ điển: cái túi   Fri 19 Mar 2010, 18:13

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.
Về Đầu Trang Go down
hoangtin14
Mèo con


Tổng số bài gửi : 96
Join date : 08/02/2010
Age : 21
Đến từ : Bình Định

Bài gửiTiêu đề: Re: Bài toán cổ điển: cái túi   Fri 19 Mar 2010, 20:22

Phải có bộ test chứ? cho đề ko thế này biết đường nào làm?
Về Đầu Trang Go down
littlelee
Admin
Admin


Tổng số bài gửi : 415
Join date : 20/12/2009
Age : 21
Đến từ : Nghĩa địa

Bài gửiTiêu đề: Re: Bài toán cổ điển: cái túi   Fri 19 Mar 2010, 21:30

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 đã ^^.
Về Đầu Trang Go down
toan_9a2
Gà con


Tổng số bài gửi : 17
Join date : 03/05/2010

Bài gửiTiêu đề: Re: Bài toán cổ điển: cái túi   Thu 13 May 2010, 14:05

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.
Về Đầu Trang Go down
littlelee
Admin
Admin


Tổng số bài gửi : 415
Join date : 20/12/2009
Age : 21
Đến từ : Nghĩa địa

Bài gửiTiêu đề: Re: Bài toán cổ điển: cái túi   Fri 14 May 2010, 16:44

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
Về Đầu Trang Go down
hoangtin14
Mèo con


Tổng số bài gửi : 96
Join date : 08/02/2010
Age : 21
Đến từ : Bình Định

Bài gửiTiêu đề: Re: Bài toán cổ điển: cái túi   Fri 14 May 2010, 21:29

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ê ^^
Về Đầu Trang Go down
littlelee
Admin
Admin


Tổng số bài gửi : 415
Join date : 20/12/2009
Age : 21
Đến từ : Nghĩa địa

Bài gửiTiêu đề: Re: Bài toán cổ điển: cái túi   Sat 15 May 2010, 13:15

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
Về Đầu Trang Go down
hoangtin14
Mèo con


Tổng số bài gửi : 96
Join date : 08/02/2010
Age : 21
Đến từ : Bình Định

Bài gửiTiêu đề: Re: Bài toán cổ điển: cái túi   Sat 15 May 2010, 14:41

trường mình cũng có a,b,c.
Về Đầu Trang Go down
Sponsored content




Bài gửiTiêu đề: Re: Bài toán cổ điển: cái túi   Today at 18:50

Về Đầu Trang Go down
 
Bài toán cổ điển: cái túi
Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang 
Trang 1 trong tổng số 1 trang

Permissions in this forum:Bạn không có quyền trả lời bài viết
Diễn đàn tin học Nguyễn Văn Linh :: Góc tin học :: Lớp chuyên tin-
Chuyển đến