Giải thích công thức trong bài toán điển hình quy hoạch động

algorithm

(Đỗ Nam) #1

Đầu bài đây ạ :slight_smile:
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ồ :frowning: > Mình cảm ơn


(rogp10) #2

Hay viết gọn hơn là L[t] ||= L[t-a[i]] :smiley:

  1. Để ý là phải thay đổi góc nhìn (out of the box) để giải được theo QHĐ :smiley:
  2. Vì ta có thể cần hay không cần a[i] để tạo thành tổng t. Nếu cần thì do tổng ban đầu chỉ lấy đến i-1 thôi nên trừ cho a[i].

83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?