Đâ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
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.
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.