解法:多重背包+完全背包。
思路:约翰能对各种硬币使用的次数是有限的,于是对约翰做多重背包。而老板对各种硬币的使用次数是无限的,于是对老板做完全背包。然后在min出最小的答案。
Code:
#include<math.h> #include<stdio.h> #include<string.h> #include<iostream> #include<algorithm> #define maxn 101000 #define INF 1000000000 using namespace std; int c[110],v[110]; int f[maxn],g[maxn]; int main() { int n,t,i,j,k,ans; scanf("%d%d",&n,&t); int sum=0,mx=0; for (i=1; i<=n; i++)scanf("%d",&v[i]); for (i=1; i<=n; i++) { scanf("%d",&c[i]); sum+=c[i]*v[i]; //求John带的钱的总值 mx=max(mx,v[i]*v[i]); //根据某某原理,必然有若干个货币组合起来是v_max的倍数,且不大于v_max^2 }//t+mx即为找钱的上限 if (sum<t) {printf("-1\n"); return 0;} //John带的钱还买不起要买的东西,自然没有解决方案,故直接输出-1并结束程序 memset(g,63,sizeof(g)); memset(f,63,sizeof(f)); g[0]=0; f[0]=0; for (i=1; i<=n; i++) for (j=v[i]; j<=t+mx; j++) g[j]=min(g[j],g[j-v[i]]+1); //老板找j元时要花的最少纸币数量 for (i=1; i<=n; i++) { for (j=1; (j=j*v[i])!=0; k--) f[k]=min(f[k],f[k-j*v[i]]+j); //John花k元时要用的最少纸币数量。 c[i]-=j; } if (c[i]) for (k=t+mx; k>=c[i]*v[i]; k--) f[k]=min(f[k],f[k-c[i]*v[i]]+c[i]); //同上 ans=INF; for (i=t; i<=t+mx; i++)ans=min(f[i]+g[i-t],ans); printf("%d\n",ans==INF?-1:ans); return 0; }