题意：有某些硬币，已知某人分别有这些硬币数ci,卖家有这些硬币无限数量，已知待买的商品价格，求这个人所花的硬币数加上找零的硬币数的和最少是多少
思路：不难看出一个多重背包和完全背包即可
主要难点在于那个人应该出多少钱？出钱的上界是什么，一开始我以为只要出了超过最大面额的钱就可以了，结果wa后意识到错了但也没想到如何确定上界的方法。
看了别人的博客学到：出钱的上界不会超过最大面额（mmax）的平方
反证：超过最大面额的平方所以找零的硬币数会超过最大面额值，把这些找零的所有硬币排成一列，sum[0…i]对mmax取模由鸽巢原理知：一定会出现两个模相同的，，那么这两个i,j之间的硬币就不需要产生了，所以一定不是最小硬币数的方式
//300 KB94 msC++1225 B#include<cstdio>#include<iostream>#include<cstring>#include<algorithm>using namespace std;const int inf = 0x3f3f3f3f;int n,t;int c[110],v[110];int dp2[125*125];int dp1[11000+125*125];int main(){while(~scanf("%d%d",&n,&t)){int mmax=-1;for(int i=1;i<=n;i++){scanf("%d",&v[i]);if(mmax<v[i]) mmax=v[i];}mmax*=mmax;for(int i=1;i<=n;i++)scanf("%d",&c[i]);memset(dp2,0x3f,sizeof(dp2));dp2[0]=0;for(int i=1;i<=n;i++)for(int j=v[i];j<=mmax;j++)dp2[j]=min( dp2[j],dp2[j-v[i]]+1 );memset(dp1,0x3f,sizeof(dp1));dp1[0]=0;for(int i=1;i<=n;i++)for(int k=1;c[i];k<<=1){int mul=min(k,c[i]);for(int j=t+mmax;j>=mul*v[i];j–)dp1[j]=min(dp1[j],dp1[j-mul*v[i]]+mul);c[i]-=mul;}int ans=inf;for(int i=t;i<=t+mmax;i++){if(dp1[i]>=inf||dp2[i-t]>=inf) continue;ans=min(ans,dp1[i]+dp2[i-t]);}if(ans==inf) puts("-1");else printf("%d\n",ans);}return 0;}
才会看到属于自己的那一片晴朗的天空。
