找錢問題描述：

與背包問題不同，找錢問題是結果必須是把容量全部裝滿

一.用的錢的最大最小數目

把空間開大，所需求的dp值只是其中的一種特殊情況而已

1.01背包模型，每種貨幣只能用一次
最小求法

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; int dp[50000],w[100]; const int MAX = 50000; const int inf = 0x3f3f3f3f; int n,m; int main() {while(~scanf("%d%d",&n,&m)){for(int i = 1;i <= n ; i++)scanf("%d%d",&w[i]);for(int i = 1; i <= MAX ;i++)dp[i] = inf;dp[0] = 0;for(int i = 1; i <= n; i++){for(int j = MAX ; j >= w[i] ;j--){dp[j] = min(dp[j],dp[j-w[i]]+1);}}if(dp[m] == inf) printf("-1\n");else printf("%d\n",dp[m]);}return 0; } View Code

最大求法 ? 只要將初始化變成-1，min改成max

2.完全背包模型，每種貨幣無限使用

把第二個for循環倒一下就行

3.多重背包模型，每一種貨幣都有數目限制

1.用完全背包和01背包

2.只用01背包*

用二進制來降低復雜度，應為所有的情況都可以用這些二進制的組合來表示，放大拆開，只要放大取出就行

最小求法，最大同理

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; int dp[50000],w[100],c[100]; const int MAX = 50000; const int inf = 0x3f3f3f3f; int n,m; void oneback(int cost,int cnt) {for(int i = MAX; i >= cost; i--)dp[i] = min(dp[i-cost]+cnt, dp[i]); } int main() {int n,m;while(~scanf("%d%d",&n,&m)){for(int i = 1; i <= n ; i++)scanf("%d%d",&w[i],&c[i]);for(int i = 1; i <= MAX;i ++)dp[i] = inf;dp[0] =0;int k;for(int i = 1; i <= n ; i++){k = 1;while(k < c[i]){oneback(k*w[i],k);c[i] -= k;k*= 2;}oneback(w[i]*c[i],c[i]);}if(dp[m] == inf) printf("-1\n");else printf("%d\n",dp[m]);} return 0; } View Code

4.多重背包模型，錢多了要找回（找回的時候是完全背包，不限數目）

最小求法

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; int dp[50000],w[100],c[100]; const int MAX = 50000; const int inf = 0x3f3f3f3f; int n,m; void oneback(int cost,int cnt) {for(int i = MAX; i >= cost; i--)dp[i] = min(dp[i-cost]+cnt, dp[i]); } void comback(int cost,int cnt) {for(int i = MAX+cost ; i >= 0 ; i--)dp[i] = min(dp[i-cost]+cnt,dp[i]); } int main() {int n,m;while(~scanf("%d%d",&n,&m)){for(int i = 1; i <= n ; i++)scanf("%d%d",&w[i],&c[i]);for(int i = 1; i <= MAX;i ++)dp[i] = inf;dp[0] =0;int k;for(int i = 1; i <= 2*n ; i++){//這樣寫方便,沒有什么特殊的含義。。if(i <= n){k = 1;while(k < c[i]){oneback(k*w[i],k);c[i] -= k;k*= 2;}oneback(w[i]*c[i],c[i]);}}else comback(-w[i-n],1);}if(dp[m] == inf) printf("-1\n");else printf("%d\n",dp[m]);} return 0; } View Code

?完全背包是從小到大的，但是負數，把循環方向改變一下。循環條件的該表只是要適應下面dp值的改變

5.記錄路徑的多重背包模型（完全背包和01背包只要把if條件改一下）

最大求法

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; int dp[10000],w[10000],num[10000],t[10000],path[10000],ans[10000]; const int MAX = 50000; const int inf = 0x3f3f3f3f; int n,m; int main() {while(~scanf("%d%d",&n,&m)){for(int i = 1; i <= n ; i++)scanf("%d%d",&w[i],&t[i]);memset(dp,0,sizeof(dp));dp[0] = 1;for(int i = 1; i <= n ; i++){for(int j = w[i]; j <= m; j++){if(dp[j-w[i]] && dp[j-w[i]] + 1 > dp[j] && num[j-w[i]] < t[i]){dp[j] = dp[j-w[i]];num[j] = num[j-w[i]] + 1;path[j] = j - w[i];}}}int i = m;if(dp[m] > 0){while(i!=0){ans[i-path[i]]++;i = path[i];}for(int i = 1; i <= n ;i++){if(ans[i]){printf("%d:%d ",i,ans[i]);}}}}return 0; } View Code

path記錄的是當前有j錢的時候買了一件東西之后的最優路徑，因為完全背包最后解肯定是最優的所以倒推是正確的

dp只是用來判斷，那個值并不能用

最小求法

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; int v[5] = {0,1,5,10,25}; int dp[10010],ans[10010],num[10010],path[10010],t[5]; int p; const int inf = 0x3f3f3f3f; int main() {while(~scanf("%d",&p)){for(int i = 1; i <= 4; i++)scanf("%d",&t[i]);if((p+t[1]+t[2]+t[3]+t[4]) == 0) break;memset(ans,0,sizeof(ans));memset(path,0,sizeof(path));for(int i = 1; i <= 10010; i++)dp[i] = inf;dp[0] = 1;for(int i = 1; i <= 4; i++){memset(num,0,sizeof(num));for(int j = v[i]; j <= p; j++){if(dp[j-v[i]] != inf && dp[j-v[i]] + 1 < dp[j] && num[j-v[i]] < t[i]){dp[j] = dp[j-v[i]] + 1;//使得后面每一個狀態都是從前面一個得到，并且滿足兩個條件1：用去一個后的數目要比沒用去的多2：用去的硬幣數目不超過硬幣本身num[j] = num[j-v[i]] + 1;path[j] = j - v[i];//難想到。。用來記錄路徑 }}}int i = p;if(dp[p]!=inf){while(i!=0){ans[i-path[i]]++;//i-path[i] = i - ( i - v[i]) = v[i]i = path[i];//path[i]表示有i錢的時候用了一種硬幣之后的錢的數目 }printf("Throw in %d cents, %d nickels, %d dimes, and %d quarters.\n",ans[1],ans[5],ans[10],ans[25]);}else printf("Charlie cannot buy coffee.\n");}return 0; } View Code

6.

?

?

　　

轉載于:https://www.cnblogs.com/zero-begin/p/4470752.html

總結

以上是生活随笔為你收集整理的找钱问题的全部內容，希望文章能夠幫你解決所遇到的問題。

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