Cần giúp đỡ về quy hoạch động tìm tập con (không liên tiếp) có tổng chia hết cho k

TrucSam · October 28, 2019, 3:33am

Mình đang làm quen với quy hoạch động. Cụ thể là bài Tìm tập con (không liên tiếp) có tổng chia hết cho k của dãy a1, a2…ai. Mình đã tìm hiểu về cách giải và code từ nhiều nguồn khác nhau nhưng giải thích thuật toán rất chung chung mình vẫn chưa hiểu rõ. Bạn nào có thể chỉ giúp thuật toán và giải thích cụ thể không. Mấy hôm nay trong đầu chỉ toàn nghĩ đến nó.

rogp10 · October 28, 2019, 4:58am

Dạng bài “tập hợp con” này mỗi slot xét hai trường hợp là tập hợp có a[i] và tập hợp không có a[i], i = 1…n

TrucSam · October 28, 2019, 6:14am

#include <bits/stdc++.h>
#define maxSum 200
#define arrSize 51
using namespace std;
int dp[arrSize][maxSum];
bool visit[arrSize][maxSum];
int SubsetCnt(int i, int s, int arr[], int n)
{
    if (i == n) {
        if (s == 0)
            return 1;
        else
            return 0;
    }
    if (visit[i][s + maxSum])
        return dp[i][s + maxSum];
    visit[i][s + maxSum] = 1;
    dp[i][s + maxSum] = SubsetCnt(i + 1, s + arr[i], arr, n)
                        + SubsetCnt(i + 1, s, arr, n);
    return dp[i][s + maxSum];
}

Mình ko hiểu cái visit[i][maxSum] : tại sao là maxSum tại sao là visit[i][s+maxSum], ngay từ đầu mình chưa xét mà tại sao có lệnh If (visit[i][s+maxSum])
dp[i][s+maxsum] là như thế nào?

TrucSam · October 28, 2019, 6:10am

bài này là tổng bằng 0, mình tìm bài tổng chia hết cho k nhưng ko có. Định tìm cách giải đc bài này rồi quay lại bài tổng =0 nhưng đụng đâu cũng bí

rogp10 · October 28, 2019, 6:18am

visit lưu trữ đã tính ô này chưa

TrucSam · October 28, 2019, 6:21am

s+maxSum là sao vậy bạn, bạn nói rõ hơn chút được ko?

rogp10 · October 28, 2019, 10:51am

Cái này nó sai sai vì nếu s>0 thì làm gì bây giờ

TrucSam · October 28, 2019, 11:28am

Code mình ko hiểu gì luôn, chắc vì mình vẫn hiểu rõ thuật toán ntn?. Bạn cho mình thuật toán và 1 ví dụ cụ thể (số cụ thể đc ko) mình sẽ chạy tay theo cách giải của bạn chắc đỡ hơn chút

xin lỗi vì ko hiểu nên mình hỏi hơi nhiều chút bạn thông cảm và giúp mình nha

rogp10 · October 29, 2019, 12:23am

Okie.

Ta dùng một cấu trúc đánh dấu để lưu các tổng của tập con (khác rỗng ). Cấu trúc này có hai cách lưu:

Key => value. Ở đây dùng cách này cho ngắn gọn.
Mảng có chỉ số [smin = sigma(u<0, u in A) u…smax = sigma(u>0, u in A) u], hiệu chỉnh bằng cách +smin.

Cách đệ quy nhánh cận sẽ ntn

# pseudo
# gọi ngay & luôn
-> branch_bound A: Array, goal, i, smax, smin: Int (A, goal, A.length-1,
A.sum_if(x => x>0), A.sum_if(x => x<0))
    <- smin <= goal || smax >= goal || i >= 0 &&
       branch_bound(A, goal, i-1, A[i] > 0? smax - A[i] : smax,
                                  A[i] < 0? smin - A[i] : smin) ||
       branch_bound(A, goal, i-1, smax, smin)

QHĐ top-down:

Bảng QHĐ gồm n dòng và mỗi dòng chạy từ smin tới smax.

# pseudo
-> arr: Array, goal: Int
    <- true if arr.find(goal) # một phần tử
   dp = Hash.new();
   <- f-> i, goal: Int (arr.length-1,goal) # gọi ngay & luôn
      <- false if n < 0;
      <- true if goal == arr[i]; # chắc chắn khác rỗng
      dp[(arr[n], n)] = true;
      <- dp[(goal, n)] ||= self(n-1, goal-arr[n]) | self(n-1, goal) # memoization

QHĐ bottom-up

Do dòng thứ n chỉ phụ thuộc vào dòng thứ n-1 nên mảng QHĐ ta thu lại còn hai dòng như sau:

# pseudo
-> arr: Array, goal: Int
   <- true if arr.find(goal) # một phần tử
   dp_from, dp_to = Hash.new, Hash.new
   for v in arr:
      dp_from, dp_to = dp_to, dp_from;
      dp_to[v] = true;
      for k in dp_from.keys():
          dp_to[k] = true; # cập nhật key từ dp_from vừa load xong
          dp_to[v+k] = true;
      <- true if dp_to[goal]
   <- false

Phần truy vết xin dành cho bạn đọc.

TrucSam · October 29, 2019, 12:07am

Cảm ơn bạn rất nhiều