Giải thích công thức trong bài toán điển hình quy hoạch động
Đầu bài đây ạ
Dãy con có tổng bằng S:
Cho dãy a1,a2,…an. Tìm một dãy con của dãy đó có tổng bằng S.
Hướng dẫn
Đặt L[i,t)=1 nếu có thể tạo ra tổng t từ một dãy con của dãy gồm các phần tử a1,a2,…ai. Ngược
lại thì L[i,t)=0. Nếu L[n,S)=1 thì đáp án của bài toán trên là “có”.
Ta có thể tính L[i,t] theo công thức: L[i,t]=1 nếu L[i–1,t]=1 hoặc L[i–1,t–a[i]]=1.
Cài đặt
Nếu áp dụng luôn công thức trên thì ta cần dùng bảng phương án hai chiều. Ta có thể nhận
xét rằng để tính dòng thứ i, ta chỉ cần dòng i–1. Bảng phương án khi đó chỉ cần 1 mảng 1
chiều L[0…S] và được tính như sau:
l[0] = 1;
for (int i=1;i<=n;i++)
for (int t=s;t>=a[i];t–)
if (l[t]==0 && l[t-a[i]] ==1) l[t] = 1;
Mọi người cho mình hỏi công thức trên lấy ở đâu và vì sao lại có nó ạ. “Ta có thể tính L[i,t] theo công thức: L[i,t]=1 nếu L[i–1,t]=1 hoặc L[i–1,t–a[i]]=1” và tiếp là khi chuyển sang mảng 1 chiều để thực hiện . Mình thật sự rất mơ hồ > Mình cảm ơn
