算法 动态规划实现找零钱问题（C/++语言）

设一硬币系统有n种面值，第i种硬币的面值和重量分别为pi​和wi​，硬币面值的单位为元，且有p1​

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

设Fk​(y)表示使用前k种硬币去找y元钱时所找硬币的最轻总重量，则Fk​(y)的递推方程定义如下： Fk​(y)=⎩⎨⎧​0≤xk​≤⌊pk​y​⌋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 #include 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 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; }

推荐文章