資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會研究
時尚研究
法學採用陣列元素和重複來求和並將結果設為 N（C++ 程式碼）的方法
本題目提供了一個數組和一個數字 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
更新於： 17-Jul-2020
587 次瀏覽
廣告