動態(tài)規(guī)劃經典題。
屬于每種物品數(shù)目可以任意的背包問題。
#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;
}