Trong bài toán này, chúng ta được cho một mảng số nguyên và một số N. Nhiệm vụ là đếm tổng số cách N có thể tạo ra bằng cách cộng các phần tử của mảng. Tất cả tổ hợp và lặp lại đều được phép.
Hãy xem ví dụ để hiểu bài toán,
Đầu vào
arr = {1, 3, 5} N = 6Đầu ra
8
Giải thích
Các cách là:
5+1, 1+5, 3+3, 3+1+1+1, 1+3+1+1, 1+1+3+1, 1+1+1+3, 1+1+1+1+1+1
Để giải bài toán này, chúng ta cần cách tiếp cận khác vì tất cả các loại tổ hợp sẽ được xử lý khác nhau, nên nếu số là tổng của 4 phần tử mảng thì 4 cách khác nhau được xem xét (như trong ví dụ). Để giải quyết bài toán như vậy, chúng ta cần dùng cách tiếp cận quy hoạch động và chương trình dưới sẽ minh họa triển khai.
Ví dụ
#include <iostream> #include <cstring> using namespace std; int arraySumWays(int array[], int size, int N){ int count[N + 1]; memset(count, 0, sizeof(count)); count[0] = 1; for (int i = 1; i <= N; i++) for (int j = 0; j < size; j++) if (i >= array[j]) count[i] += count[i - array[j]]; return count[N]; } int main() { int array[] = {1, 5, 6}; int size = sizeof(array) / sizeof(array[0]); int N = 7; cout<<"Tổng số cách "<<N<<" có thể tạo ra bằng tổng phần tử mảng là " <<arraySumWays(array, size, N); return 0; }Đầu ra
Tổng số cách 7 có thể tạo ra bằng tổng phần tử mảng là 6