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

#1

Em đã tim được thuật toán và code được bài:

Cho dãy n số tự nhiên a1, a2,…, an và số tự nhiên S. Hỏi tồn tại dãy con có tổng S bằng cách cộng một số phần tử trong dãy A không.
Cho dãy a1, a2,…, an. Tìm một dãy con của dãy đó có tổng bằng S.

Input

  • Dòng 1 chứa 2 số n, S. (0 < n, S ≤ 1000)
  • Dòng tiếp theo, ghi n số a1, a2, …, ai (|ai| ≤ 1000)

Output: Xuất ra số 1 nếu tồn tại dãy con thỏa để bài, ngược lại thì xuất 0.

Thuật toán của em cũng khá đơn giả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.

Nhưng mà em thắc mắc là làm sao để đếm đc số dãy con có tổng bằng S ạ. Em phát triển từ thuật toán này nhưng thấy không thể ra được đáp án nên hi vong các anh xem qua và cho em xin ý kiến ạ.

1 Like
#2

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]]
1 Like
#3

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í ạ

#4

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

#5

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 à.

#6

A post was merged into an existing topic: Topic lưu trữ các post off-topic - version 3

#7

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ố.

#8

Đặ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 ạ.

#9 
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];
#10

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.

#11

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 đó :slight_smile: (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à :smiley:

Cộng cả 2 trường hợp trên lại thì ta có giá trị L[i][j] :slight_smile: đơn giản vì nó bao quát hết khả năng và không giao nhau :slight_smile: (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 :slight_smile: 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ế :slight_smile: 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ỏ

2 Likes
#12

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

#13

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 :smiley: 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).

1 Like
#14

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

#15

Còn thiếu a[i] == j nữa.
Truy vết thì dựa trên công thức thôi :slight_smile: 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 0/1 là L[i][j] = (a[i] == j) OR L[i-1][j] OR L[i-1][j-a[i]], L[0][s] = false.

1 Like
#16

Nếu đề cho m <= 1e6 thì bác nào có cách khác không ?
Cách của em :

  • Tạo mảng cộng dồn f[i] = a[i] + a[i-1];
  • sắp xếp lại mảng f và chặt nhị phân.
#17

Bạn cho mình xin ý tưởng cách giải bài toán đếm số dãy con có tổng <k và các a[i] có số âm và số dương.

#18

Tổng các số âm sẽ ứng với ô 0, hay tổng S ứng với a[S trừ tổng các số âm].

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