質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
C++11

C++11は2011年に容認されたC++のISO標準です。以前のC++03に代わるもので、中枢の言語の変更・修正、標準ライブラリの拡張・改善を加えたものです。

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

Q&A

解決済

1回答

2800閲覧

動的計画法のプログラムを作成したのですが、なぜか答えがずれてしまいます

tukejonny

総合スコア50

C++11

C++11は2011年に容認されたC++のISO標準です。以前のC++03に代わるもので、中枢の言語の変更・修正、標準ライブラリの拡張・改善を加えたものです。

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

0グッド

0クリップ

投稿2015/01/07 11:31

プログラミング初心者なので、温かい目で見ていただけると幸いです。
動的計画法について勉強したてなのですが、以下の問題について動的計画法で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円支払う際の最小枚数が間違っているようなのです。
原因について考えてみたのですが、わかりません。
どなたか教えていただけないでしょうか?

また、動的計画法について、プログラミングコンテストチャレンジブックという本のアルゴリズムを写経しながら勉強している途中なので、理解が薄い状況です。誠に身勝手ですが、その点も踏まえて回答していただけると嬉しいです。

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答1

0

ベストアンサー

15は5Gが3枚、20は5Gが4枚がそれぞれ最小で合ってると思います。

投稿2015/01/07 12:59

argius

総合スコア9388

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

tukejonny

2015/01/07 13:45

回答ありがとうございます!! 全然気がつきませんでした・・・(自分がアホゥですみません・・・ 目から鱗が落ちました!
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問