前言

开始以为是搜索，按照不同物品不同数量枚举，超时。又在这基础上剪枝，考虑了币值之间的倍数关系，想把一个货币体系化简为货币值之间互质的情形，但写了一下感觉太复杂了。又按照钱数递减搜索，每次减去某一种币值并去掉重复情况…搞了n久还是超时，唉~。最后感觉可能是动态规划，但想不出个所以然来。无奈只好求助于nocow，发现这货竟然是背包！

没往背包上想可能是因为这个背包问题没用到物品价值这一属性吧，换句话说这个背包并不是要求出某一条件下的最大价值。

题目大意

有v种币值和一个钱数n，问用给定币值可以有多少种方案构成n。

思路

完全背包。有v种物品（v种币值），每种物品对应固定的费用（币值），背包的总容量为n（钱数），求有多少种情况能使背包恰好装满。

代码

/*
ID: lujunda1
LANG: C++
PROG: money
*/
#include<iostream>
#include<stdio.h>
#include<cstring>
using namespace std;

int N,V;
//N种物品，背包容量为V。
int c[25];
//c[]用来存储费用。 
long long f[10001];
//f[i]总钱数为i时的最大方法数。
 
int main()
{
	freopen("money.in","r",stdin);
	freopen("money.out","w",stdout);
	memset(f,0,sizeof(f[0]));
	scanf("%d%d",&N,&V);
	for(int i=0;i<N;i++)
		scanf("%d",&c[i]);
	f[0]=1;
	for(int i=0;i<N;i++)
		for(int v=c[i];v<=V;v++)
			f[v]+=f[v-c[i]];
	printf("%lld\n",f[V]);
}