《算法设计与分析》实验报告3

 

实验名称: 货币支付问题

系    别:xxx           

专    业:xxx           

班    级:xxx

姓    名:xxx          

学    号:xxx

实验日期:xx年xx月xx日

 

1.  算法题目

根据动态规划法的设计思想和算法步骤，要求学生设计一个动态规划算法，用于解决货币支付的问 题。n种货币面额的纸币，需要支付y价值的商品，问如何出最少的货币张数。可以先处理只支付一 种面额的货币，再处理支付两种面额的货币，再处理支付三种面额的货币，......。后一个方案，可 以基于前一个方案，通过追加不同面额的货币得到。因此，可以用动态规划算法解决该问题。

 

2.  设计思路与步骤

定义钱币种类数组coins[]和动态规划数组dp[];初始化dp和coins；找出动态规划条件如下：

if(i >= coins[j] && dp[i - coins[j]] + 1 < dp[i]){  

                dp[i] = dp[i- coins[j] ] + 1;

            }

填表即可得出dp[money]即为最优解。

 

3.  算法实现与代码

#include<stdio.h>

int main() {

int coins[10000];

int dp[10000];

int kind;

int i;

int j;

int money;

printf("请输入货币的种类：");

scanf("%d", &kind);

for(i = 0; i < kind; i++) {

printf("请输入第%d种货币的面值：\n", i + 1);

scanf("%d", &coins[i]);

}

printf("请输入待支付的金额(money<=10000):");

scanf("%d", &money);

dp[0] = 0;

for(i = 1; i <= money; i++)

dp[i] = 65535;

for(i = 1; i <= money; i++) {

for(j = 0; j < kind; j++){

if(i >= coins[j] && dp[i - coins[j]] + 1 < dp[i]){  

                dp[i] = dp[i- coins[j] ] + 1;

            }

        }

}

if(dp[money] == 65535)

printf("支付失败！\n");

else

printf("最少货币数为%d\n", dp[money]);

return 0;

}

 

4.  测试用例与结果

答：xxx。