总结特定数字以获得100的不同方式

Question

我想写一个代码来显示有多少种方法可以总结5个不同的数字来得到100.例如,数字是2,5,10,20,50,并且它们可以重复任意次.这50+50是一种方式20+20+20+20+20.我不知道如何编程.

我认为它应该通过递归函数完成,我试着写一个而不知道如何,所以这是我想出的最好的:

#include<iostream>
#include<vector>

using namespace std;


int i,sum,n=5,counter=0;


int add(vector<int> &m){

    if(m.size()==0) return 0 ;

    for(i=0 ; i<m.size() ; i++ ){

          sum=m[i]+add(m);
          cout<< sum<<endl;
        if(n>0) n--;
        m.resize(n);
    }


}


int _tmain(int argc, _TCHAR* argv[])
{
    int i,sum,n=5;

vector<int> m;

m.resize(5);

m[0]=2;
m[1]=5;
m[2]=10;
m[3]=20;
m[4]=50;

add(m);


    return 0;
}

Answer 1

使用生成函数可以在理论上解决该问题.生成函数不是一个函数,它不生成任何东西(好名字,嗯？),但它确实可以很好地跟踪信息.其结果是,在回答你的问题是,如何在数量等于系数x^100在扩大

1/(1-x^2) * 1/(1-x^5) * 1/(1-x^10) * 1/(1-x^20) * 1/(1-x^50) 

以下是对原因的解释.回想一下1/(1-x) = 1 + x + x^2 + x^3 + ....这是我们将用于解决问题的基本生成函数.

考虑你有数字A,B,...,N(在你的例子中,它们是2,5,10,20,50)你可以重复任意次.然后考虑(生成)函数

f(x) = 1/(1-x^A) * 1/(1-x^B) * ... * 1/(1-x^N)

x^Min 的系数f(x)是M作为表格总和写入的方式的数量

M = a*A + b*B + ... + n*N

哪里a,b,...,n是非负整数.

为什么这样做？因为在扩张任何单项项f(x)来源于采取一个长期的1/(1-x^A),这将看起来像x^(a*A)一些非负a,和类似的其他条款.既然指数加了,系数x^M就是写出这样一个总和得到的所有方法M.

我知道这不是一个编程答案,但希望你能用这个想法编写一个程序.