Diễn đàn tin học Nguyễn Văn Linh
Bạn có muốn phản ứng với tin nhắn này? Vui lòng đăng ký diễn đàn trong một vài cú nhấp chuột hoặc đăng nhập để tiếp tục.

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

The second house for every one
 
Trang ChínhLatest imagesTìm kiếmĐăng kýĐăng Nhập

 

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

Go down 
3 posters
Tác giảThông điệp
littlelee
Admin
Admin
littlelee


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

Bài toán cổ điển: cái túi Empty
Bài gửiTiêu đề: Bài toán cổ điển: cái túi   Bài toán cổ điển: cái túi I_icon_minitimeFri 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
hoangtin14


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

Bài toán cổ điển: cái túi Empty
Bài gửiTiêu đề: Re: Bài toán cổ điển: cái túi   Bài toán cổ điển: cái túi I_icon_minitimeFri 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
littlelee


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

Bài toán cổ điển: cái túi Empty
Bài gửiTiêu đề: Re: Bài toán cổ điển: cái túi   Bài toán cổ điển: cái túi I_icon_minitimeFri 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
toan_9a2


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

Bài toán cổ điển: cái túi Empty
Bài gửiTiêu đề: Re: Bài toán cổ điển: cái túi   Bài toán cổ điển: cái túi I_icon_minitimeThu 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
littlelee


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

Bài toán cổ điển: cái túi Empty
Bài gửiTiêu đề: Re: Bài toán cổ điển: cái túi   Bài toán cổ điển: cái túi I_icon_minitimeFri 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
hoangtin14


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

Bài toán cổ điển: cái túi Empty
Bài gửiTiêu đề: Re: Bài toán cổ điển: cái túi   Bài toán cổ điển: cái túi I_icon_minitimeFri 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
littlelee


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

Bài toán cổ điển: cái túi Empty
Bài gửiTiêu đề: Re: Bài toán cổ điển: cái túi   Bài toán cổ điển: cái túi I_icon_minitimeSat 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
hoangtin14


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

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

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





Bài toán cổ điển: cái túi Empty
Bài gửiTiêu đề: Re: Bài toán cổ điển: cái túi   Bài toán cổ điển: cái túi I_icon_minitime

Về Đầu Trang Go down
 
Bài toán cổ điển: cái túi
Về Đầu Trang 
Trang 1 trong tổng số 1 trang
 Similar topics
-
» Điện Ảnh Và OSCAR
» Đố một bài toán, xếp mảng
» Bài toán liệt kê
» lời thề và bài toán tình yêu
» Các thuật toán sắp xếp |sắp xếp đổi chỗ|

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