Gia sư Cần Thơ, Dạy Kèm Cần Thơ

VỮNG TIN - TIẾP BƯỚC - THÀNH CÔNG


Bài 12. Bài toán balo giải bằng đệ quy

Share

qvluom
Sơ cấp
Sơ cấp

Tổng số bài gửi : 23
Points : 29
Join date : 26/11/2009

Bài 12. Bài toán balo giải bằng đệ quy

Bài gửi  qvluom on Sat Nov 28, 2009 8:26 am

Đây là bài toán khá nổi tiếng với phương pháp quy hoạch động. Tuy nhiên ở đây tôi trình bày lại bằng phương pháp đệ quy để các bạn tham khảo (nhưng tuyệt đối không được áp dụng vì quy hoạch động hay hơn)
1. Phát biễu bài toán:
Có một cái ba lô có sức chứa là m kg (bài toán này không đề cập đến thể tích chứa của ba lô). Bạn có n vật nặng, mỗi vật có khối lượng là a[i] (i = 1->n). Hãy tìm cách bỏ các vật nặng này vào ba lô (chú ý không được quá tải) sao cho tổng khối lượng các vật chứa trong ba lô là lớn nhất.

2. Code Pascal
Code:
Function max(a,b:longint):longint;
Begin
  max:=a;
  If a<b then max:=b;
End;
Function try(n,m:longint):longint;
Begin
 If m=0 then try:=0 else if n=1 then
  Begin
      If  a[1]<= m then try:=a[1] else try:=0;
  End
 Else if m< a[n] then try:= try(n-1,m)
 Else try:= max(try(n-1,m), try(n-1, m- a[n])+ a[n]);
End;

Alpha xem góp ý cho mình.
À mà sao Alpha không lập ra đề mục giải các bài toán khác phục vụ cho các sinh viên có ý định tham dự Olympic Tin học sinh viên.

qvluom
Sơ cấp
Sơ cấp

Tổng số bài gửi : 23
Points : 29
Join date : 26/11/2009

Re: Bài 12. Bài toán balo giải bằng đệ quy

Bài gửi  qvluom on Sat Nov 28, 2009 8:29 am

Cáo lỗi một tí. Hàm max của mình nó bị loạn xạ hết rồi. Các bạn tự chỉnh sửa lại nhé.

    Hôm nay: Mon Nov 20, 2017 4:27 pm