Xin ý tưởng về thuật toán Quy hoạch động

Theo mình nghĩ thế này. Ta có thể cải tiến = cách dùng mảng L để lưu số trường hợp để có khối lượng t

Nếu t-a[i]<0: L[i,a[i]]+=1
Nếu t>=a[i]: L[i,t]+=L[i-1][t]+L[i-1][t-a[i]]

Vậy ý nghĩa thằng mảng L[i,t] của bác là gì thế giải thích cho em với. Em mới bắt đầu học phần này nên hơi dở tí ạ

Mảng L[i,t] sẽ đếm số cấu hình mà tại đó i phần tử đầu sẽ có tổng là t

Do vậy nên nếu l[i-1,t]=1 thì thằng l[i,t]=1 nên em chưa làm cách nào mà đếm được số cách à.

Liên hệ facebook https://m.facebook.com/home.php#!/profile.php?ref=bookmarks

Bạn có thể làm 1 mảng khác ví dụ l[i]]j] cũng tương tự như trên như chỉ khác là số cách lập thành số j từ tổng của i số.

Đặt mảng L như bạn mình cũng nghĩ đến rồi nhưng mà hiện h chưa nghĩ được thuật toán ạ. Hi vọng anh có thể gợi ý cho em đôi chút ạ.

Gió không chém đâu :smiley:
L[i][j] là số cách tạo nên tổng bằng j sử dụng i phần tử ban đầu

khởi tạo l[i][0]=1;
if(j>=a[i])
      L[i][j]= l[i-1][j]+ l[i-1][j-a[i]];
else
      L[i][j]= l[i-1][j];

Bác AI_ANdroid có thể giải thích rõ thuật toán và tại sao mình lại có như vậy được không.

Với L[i][j] là số cách tạo nên tổng bằng j sử dụng i phần tử ban đầu
Xét phần tử thứ i
Có và chỉ có 2 trường hợp xẩy ra.
1=> ta ghép nó vào làm 1 số hạng để tạo thành tổng j. => số cách tạo thành tổng j bằng số cách tạo thành tổng j-a[i] bằng các số hạng trước đó (tại vì sau đó ta thêm số a[i] vào là được j rồi )
2=> ta bỏ qua nó => số cách tạo thành tổng j dùng i phần từ sẽ bằng số cách tạo thành tổng j dùng i-1 phần tử vì thực tế ta bỏ qua nó mà

Cộng cả 2 trường hợp trên lại thì ta có giá trị L[i][j] đơn giản vì nó bao quát hết khả năng và không giao nhau (1 th có a[i] 1 trường hợp không có a[i] trùng thế nào đc nhỉ )

Ví dụ: cho chuỗi 1 1 2 3
Tìm số cách tạo thành tổng S=4;
Khởi tạo F[0->4,0]=1 có duy nhất 1 cách đó là không chọn số nào
F[1,1]= F[0,1]+ F[0,0] =1;
F[1,2]=F[0,2]=0;F[1,3]=0;F[1,4]=0;

Tương tự thế cách nhanh nhất để kiểm tra 1 thuật toán có đúng trong các trường hợp khái quát không là viết ra các bước của nó chạy với 1 test nhỏ nhỏ

Công nhân anh giải thích dễ hiểu ghê, đọc phát là em hiểu được bản chất với cái công thức luôn. Vậy mà mấy hôm nay em vật vã vì nó. HI vọng mai mốt anh có thể chỉ em mấy bài về QHĐ nữa ạ. Cảm ơn anh @Gio và anh @AI_Android

Có thêm phần đếm nữa thì chua lắm, tại vì không có điều kiện đôi một khác nhau.

Một cách mở rộng bài là nếu cho thêm số âm vào thì phải sửa như thế nào mới ra đúng Bài này là NP-complete nên chạy lâu cực kỳ.

p/s: https://arxiv.org/abs/1507.02318 có cả sum (mod m).

Thế có cách nào truy vết dãy con đó không?

Còn thiếu a[i] == j nữa.
Truy vết thì dựa trên công thức thôi chỉ có hai khả năng: bỏ qua (zero) hoặc chọn a[i] (1). Vậy mỗi slot chỉ cần 1 byte, vừa truy vết vừa tính.

Biểu thức cho bài Y/N là L[i][j] = (a[i] == j) OR L[i-1][j] OR L[i-1][j-a[i]], L[0][s] = false.