动态规划经典题。
属于每种物品数目可以任意的背包问题。
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("money.in");
ofstream fout("money.out");
#ifdef _DEBUG
#define out cout
#define in cin
#else
#define out fout
#define in fin
#endif
long long dp[10001];
int coins[25];
void solve()
{
dp[0] = 1;
int v,n;
in>>v>>n;
for(int i=0;i<v;++i)
in>>coins[i];
for(int i=0;i<v;++i){
for(int j=0;j+coins[i]<=n;++j){
dp[j+coins[i]]+=dp[j];
}
}
out<<dp[n]<<endl;
}
int main(int argc,char *argv[])
{
solve();
return 0;
}