动态规划实现找零钱问题（C/++语言）-Toy模板网

这篇具有很好参考价值的文章主要介绍了动态规划实现找零钱问题（C/++语言）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

设一硬币系统有n种面值，第i种硬币的面值和重量分别为pi和wi，硬币面值的单位为元，且有p1<p2<⋯<pn和p1=1，现需要给别人找Y∈Z+元钱，试确定一找零钱方案，使得所找的硬币的总重量最轻。

要求使用如下动态规划思想

设Fk(y)表示使用前k种硬币去找y元钱时所找硬币的最轻总重量，则Fk(y)的递推方程定义如下：
Fk(y)=⎩⎨⎧0≤xk≤⌊pky⌋min{xk⋅wk+Fk−1(y−xk⋅pk)},y⋅w1,k>1k=1

设xk(y)表示Fk(y)取得最小值时第k种硬币所找的硬币数xk，为了能够方便构造最优解，需要每算出一个Fk(y)时，记录一下对应的xk(y)。

输入格式:

输入共三行正整数，具体要求如下：

第1行输入两个正整数，以一个空格隔开，分别代表硬币种数n和要找的钱数Y
第2行输入n个正整数，以一个空格隔开，分别代表n种硬币的面值。要求：n种硬币的面值必须呈现单调递增，且第1种硬币的面值必须是1
第3行输入n个正整数，以一个空格隔开，分别代表n种硬币的重量

输出格式:

输出两行，具体要求如下：

第1行输出每种面值所找的硬币数，以一个空格隔开
第2行输出所找硬币的总重量

输入样例: 4 28
1 5 14 18
1 1 1 1

输出样例: 0 0 2 0
2

代码：

#include<stdio.h>
#include<stack>
using namespace std;
#define maxn 1010
int n, y;
int p[maxn], w[maxn], F[maxn][maxn], x[maxn][maxn];

int main(){
   scanf("%d%d", &n, &y);
   for(int i=1; i<=n; i++){
       scanf("%d", &p[i]);
   }
   for(int i=1; i<=n; i++){
       scanf("%d", &w[i]);
   }
   for(int i=0; i<=y; i++){
       F[1][i] = i*w[1];
       x[1][i] = i;
   }
   for(int i=2; i<=n; i++){
       F[i][0] = 0;
       x[i][0] = 0;
   }
   for(int k=2; k<=n; k++){
       for(int j=1; j<=y; j++){
           int m = j/p[k];
           F[k][j] = F[k-1][j-m*p[k]]+m*w[k];
           x[k][j] = m;
           for(int i=0; i<m; i++){
               int a=i*w[k]+F[k-1][j-i*p[k]];
               if(a<F[k][j]){
                   F[k][j] = a;
                   x[k][j] = i;
               }
           }
       }
   }
   stack<int> st;
   int Y=y, k=n;
   while(1){
       if(!k){
           break;
       }
       st.push(x[k][y]);
       y -= x[k][y]*p[k];
       k--;
   }
printf("%d", st.top());
   st.pop();
   while(st.size()){
       printf(" %d", st.top());
       st.pop();
   }
   printf("\n%d", F[n][Y]);
   return 0;
}文章来源地址https://www.toymoban.com/news/detail-773749.html