《算法設(shè)計與分析》實驗報告3

?

實驗名稱: 貨幣支付問題

系????別:xxx???????????

專????業(yè):xxx? ? ? ? ? ?

班????級:xxx

姓????名:xxx? ? ? ? ??

學(xué)????號:xxx

實驗日期:xx年xx月xx日

?

1. ?算法題目

根據(jù)動態(tài)規(guī)劃法的設(shè)計思想和算法步驟，要求學(xué)生設(shè)計一個動態(tài)規(guī)劃算法，用于解決貨幣支付的問 題。n種貨幣面額的紙幣，需要支付y價值的商品，問如何出最少的貨幣張數(shù)?？梢韵忍幚碇恢Ц兑?種面額的貨幣，再處理支付兩種面額的貨幣，再處理支付三種面額的貨幣，......。后一個方案，可 以基于前一個方案，通過追加不同面額的貨幣得到。因此，可以用動態(tài)規(guī)劃算法解決該問題。

?

2. ?設(shè)計思路與步驟

定義錢幣種類數(shù)組coins[]和動態(tài)規(guī)劃數(shù)組dp[];初始化dp和coins；找出動態(tài)規(guī)劃條件如下：

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

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

????????????}

填表即可得出dp[money]即為最優(yōu)解。

?

3. ?算法實現(xiàn)與代碼

#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("最少貨幣數(shù)為%d\n", dp[money]);

return 0;

}

?

4. ?測試用例與結(jié)果

答：xxx。

?