將?Xiaoqian可付的錢的值用多重背包的方式計算拼湊起來所需的最小硬幣數，用完全背包的方式計算找錢的值的拼湊最小硬幣數。然后再尋找最小值。

?

#include<algorithm> #include<iostream> #include<cstring> #include<cstdio> using namespace std; int dp1[20005], dp2[20005], t, v[105], r[105]; const int INF=1<<29; void deal1(int x) {int i;if(v[x]*r[x]>=20000){for(i=v[x];i<=20000;i++){dp1[i]=min(dp1[i],dp1[i-v[x]]+1);}}else{int k=1;while(k<r[x]){for(i=20000;i>=k*v[x];i--)dp1[i]=min(dp1[i],dp1[i-k*v[x]]+k);r[x]-=k;k*=2;}for(i=20000;i>=r[x]*v[x];i--)dp1[i]=min(dp1[i],dp1[i-r[x]*v[x]]+r[x]);} } void deal2(int x) {int i;for(i=v[x];i<=20000;i++){dp2[i]=min(dp2[i],dp2[i-v[x]]+1);} } int main() {int n, i, nc=0;while(scanf("%d%d",&n,&t)!=EOF){if(n==0&&t==0) break;for(i=0;i<n;i++)scanf("%d",&v[i]);for(i=0;i<n;i++)scanf("%d",&r[i]);dp1[0]=dp2[0]=0;for(i=1;i<=20000;i++)dp1[i]=dp2[i]=INF;for(i=0;i<n;i++)deal1(i);for(i=0;i<n;i++)deal2(i);int ans=INF;for(i=20000;i>=t;i--){if(dp1[i]!=INF&&dp2[i-t]!=INF)ans=min(ans,dp1[i]+dp2[i-t]);}printf("Case %d: ",++nc);if(ans==INF)printf("-1\n");elseprintf("%d\n",ans);}return 0; }

?

轉載于:https://www.cnblogs.com/ink-syk/p/3315153.html

總結

以上是生活随笔為你收集整理的HDU 3591 The trouble of Xiaoqian的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。