Bài toán TRANSPORT

[Nobita004 (Kirito-kun)]

Cho em hỏi bài toán:
Cho dãy a1,a2,…,an và số m. Tìm tổng lớn nhất của dãy con mảng a bé hơn m.
Ví dụ: 5 10
3 4 2 3 5
Thì kết quả in ra sẽ là 9.

Cách làm của em như sau:

#include <bits/stdc++.h>
using namespace std;

int main() {
	// your code goes here
	int n,m,F[100][100],a[100];
	cin>>n>>m;
	for (int i=1;i<=n;i++) cin>>a[i];
	for (int i=0;i<=m;i++) F[0][i]=0; 
	for (int i=1;i<=n;i++)
	   for (int j=1;j<=m;j++){
	   	  F[i][j]=F[i-1][j];
	   	  if (j-a[i]>0) F[i][j]=max(F[i][j],a[i]+F[i-1][j-a[i]]);
	   }
	cout<<F[n][m];
	return 0;
}

Em cho kết quả đúng nhưng khi chấm bài thì vẫn có test chạy quá thời gian. Mọi người coi xem em sai chỗ nào được không? Hoặc có cách nào đó nhanh hơn chẳng hạn! Em cảm ơn!

Link code: https://ideone.com/32jCV3

[rogp10]

Thuật toán này kinh điển rồi chỉ có code không khéo.

Đây là trường hợp riêng của bài túi kẹo.

[Nobita004 (Kirito-kun)]

Bạn cho mình xin link bài toán được không? Tại mình mới học quy hoạch động nên chưa biết nhiều!
Mình cảm ơn!

[rogp10]

Sách GT&LT của thầy Lê Minh Hoàng quyển này dễ tìm hơn.

Do F[i] chỉ phụ thuộc vào F[i-1] nên có thể chỉ dùng 2 mảng một chiều.
Do F[i][j] chỉ phụ thuộc vào F[i-1][các slot trước j] và chính nó nên gộp lại thành một mảng duy nhất có m + O(1) slot mem.

Độ phức tạp là theta(m*n) time.

---

Ban đầu mình cũng chả hiểu sao lại chạy j từ 1 đến max túi cho đến khi dùng đệ quy để tính số cách bỏ vào túi.