Subset Sum - Quy hoạch động phần 1

    Bài viết trước chúng ta đã cùng nhau giải bài toán Subset Sum sử dụng Backtracking (đệ quy quay lui), ở bài viết này chúng ta sẽ giải quyết chúng bằng thuật toán quy hoạch động (Dynamic Programing) nhé! Yêu cầu bài toán đặt ra là đếm số cách chọn phần tử trong mảng để được tổng là m, biết rằng các phần tử trong các phần tử trong mảng được sử dụng thoải mái. Bài toán này chính là cách phát biểu khác của bài Knapsac, đổi tiền (cashier), ...

1. Thứ tự khác nhau được coi là hai cách chọn khác nhau

int C[MAX]; //C[i] = k là số cách chọn để được tổng i 
int SubsetSum(int arr[], int n, int m){
  C[0] = 1;
  for(int i = 1; i <= m; i++){
    for(int j = 0; j < n; j++){
      if(i - arr[j] < 0)
        continue;
      C[i] += C[i - arr[j]];
    }
  }

  return C[m];
}

2. Thứ tự các phần tử trong mảng là không quan trọng

int C[MAX];
int UniqueSubsetSum(int arr[], int n, int m){
  C[0] = 1;
  for(int i = 0; i < n; i++){
    for(int j = arr[i]; j <= m; j++)
      C[j] += C[j - arr[i]];
  }

  return C[m];
}

Hẹn gặp lại mọi người ở bài viết sau!