多重背包+完全背包。
买家：多重背包；售货员：完全背包；
开两个数组，分别计算出买家，售货员每个面额的最少张数。
最重要的是上界的处理：上界为maxw*maxw+m（maxw最大面额的纸币）。
（网上的证明）证明如下：
如果买家的付款数大于了maxw*maxw+m，即付硬币的数目大于了maxw，根据鸽笼原理，至少有两个的和对maxw取模的值相等，也就是说，这部分硬币能够用更少的maxw来代替。证毕。
其实我真心没看懂这个证明。不过我们可以猜想T一定不会太大，我开了10*T然后过了。
这一题学习了多重背包：
http://www.cnblogs.com/favourmeng/archive/2012/09/07/2675580.html
1 #include<cstdio>
2 #include<cstdlib>
3 #include<cstring>
4 #include<cmath>
5 #include<iostream>
6 #include<algorithm>
7 using namespace std;
8
9 const int N=110,S=100100,INF=(int)1e9;
10 int n,T,mx,v[N],c[N],f[S],g[S];
11 int minn(int x,int y){return x<y ? x:y;}
12 int maxx(int x,int y){return x>y ? x:y;}
13
14 int main()
15 {
16 // freopen("a.in","r",stdin);
17 freopen("fewcoins.in","r",stdin);
18 freopen("fewcoins.out","w",stdout);
19 scanf("%d%d",&n,&T);
20 mx=0;
21 for(int i=1;i<=n;i++) {scanf("%d",&v[i]);mx=maxx(mx,v[i]);}
22 for(int i=1;i<=n;i++) scanf("%d",&c[i]);
23 mx=mx*mx+T;
24 // mx=10*T;
25 memset(f,63,sizeof(f));
26 f[0]=0;
27 for(int i=1;i<=n;i++)
28 for(int j=v[i];j<=mx;j++)
29 f[j]=minn(f[j],f[j-v[i]]+1);
30
31 memset(g,63,sizeof(g));
32 g[0]=0;
33 for(int i=1;i<=n;i++)
34 {
35 int now=c[i],j=1;
36 while(now>0)
37 {
38 for(int k=mx;k>=j*v[i];k--)
39 g[k]=minn(g[k],g[k-j*v[i]]+j);
40 now-=j;
41 j*=2;
42 }
43 }
44 int ans=INF;
45 for(int i=T;i<=mx;i++)
46 ans=minn(ans,g[i]+f[i-T]);
47 if(ans==INF) printf("-1
");
48 else printf("%d
",ans);
49 return 0;
50 }