ในปัญหานี้ เราได้รับอาร์เรย์ของจำนวนเต็มและจำนวน N หน้าที่ของเราคือนับจำนวนวิธีทั้งหมดที่สร้าง N โดยการเพิ่มองค์ประกอบของอาร์เรย์ อนุญาตให้ใช้ชุดค่าผสมและการทำซ้ำทั้งหมดได้
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
อินพุต
arr = {1, 3, 5} N = 6 ผลลัพธ์
8
คำอธิบาย
วิธีการคือ −
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
ในการแก้ปัญหานี้ เราต้องใช้แนวทางที่แตกต่างออกไป เนื่องจากชุดค่าผสมทุกประเภทจะได้รับการปฏิบัติต่างกัน ดังนั้นหากตัวเลขเป็นผลรวมของ 4 องค์ประกอบของอาร์เรย์ 4 วิธีที่แตกต่างกันจะได้รับการพิจารณา (ดังแสดงในตัวอย่าง) ในการแก้ปัญหาดังกล่าว เราจำเป็นต้องใช้วิธีการเขียนโปรแกรมแบบไดนามิก และโปรแกรมด้านล่างจะแสดงการนำไปใช้
ตัวอย่าง
#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<<"Total number of ways inwhich "<<N<<" can be generated using sum of elements of array is " <<arraySumWays(array, size, N);
return 0;
} ผลลัพธ์
Total number of ways inwhich 7 can be generated using sum of elements of array is 6
