プログラミング初心者なので、温かい目で見ていただけると幸いです。
動的計画法について勉強したてなのですが、以下の問題について動的計画法でC++でプログラムを作成してみました。
lang
1 2問題文: 3ある国の硬貨は 1G,5G,12G となっている。20G までの任意の G について、払う硬貨の枚数を少なくしたい。 どのようにして求めればよいか。DPを用いてプログラムを作成せよ 4
lang
1//dp[r] := r円を払う際の最小の枚数 2#include <bits/stdc++.h> 3#define MAX_M 20 4#define INF 10000000 5using namespace std; 6int kind = 3; //硬貨の種類数 7int money[] = {1, 5, 12}; //硬貨3種類のそれぞれの価値 8int M = 20; 9 10int dp[MAX_M + 1]; 11 12//DPテーブルを出力 13void print() { 14 for(int r = 0; r <= M; r++) { 15 cout << r << "円支払う際の最小枚数:" << dp[r] << endl; 16 } 17 putchar('\n'); 18} 19 20void init() { //0円支払う時は0枚で良いということを考慮した上でDPテーブルを初期化 21 for(int r = 0; r <= MAX_M; r++) dp[r] = INF; 22 dp[0] = 0; 23} 24 25void solve() { 26 init(); 27 //M円までで最小の枚数を求める 28 for(int r = 1; r <= M; r++) { 29 for(int c = 0; c < kind; c++) { 30 for(int k = 0; k * money[c] <= r; k++) { 31 dp[r] = min(dp[r], dp[r - k*money[c]] + k); 32 } 33 } 34 } 35 printf("%d\n", dp[M]); 36} 37 38int main(void) { 39 solve(); 40 print(); 41 return(0); 42} 43
普通に考えれば、20G支払うのに12Gを1枚、5Gを1枚、1Gを3枚で計5枚が最小枚数となるはずです。
ですが、答えは4と出力されてしまいます。
どうやら、15円支払う際の最小枚数及び20円支払う際の最小枚数が間違っているようなのです。
原因について考えてみたのですが、わかりません。
どなたか教えていただけないでしょうか?
また、動的計画法について、プログラミングコンテストチャレンジブックという本のアルゴリズムを写経しながら勉強している途中なので、理解が薄い状況です。誠に身勝手ですが、その点も踏まえて回答していただけると嬉しいです。
回答1件
あなたの回答
tips
プレビュー
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
2015/01/07 13:45