数据结构
网络
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 次浏览
广告