ここから本文です

貪欲法?C言語を使った動的計画法の問題について教えてください 大学生です

kar********さん

2019/8/919:25:09

貪欲法?C言語を使った動的計画法の問題について教えてください

大学生です

独学でC言語を勉強しているのですが,動的計画法を利用して指定された金額を最小のコイン枚数で支払うという問題で悩んでいます

「コインの額面がC[0]=1,C[1]=2,C[2]=4,C[3]=7として
0<i<nのC[i]を使ってm円を支払うときの最小枚数をT[n,m]と表す
(1)T[n,m]をn'<nかm'<mを満たすT[n',m']を用いて表せ
(2)C言語を用いてT[n,m]を動的計画法により計算するcalcT(n,m)を記述せよ」
となっています.試しに書き出してみた結果を添付しています

また調べた限りですが,これは貪欲法という方法で正しいのでしょうか?
特にプログラミングでどのように記述するのがよいのかわかっておらず,教えてください
よろしくお願いします

C言語,n-m,計画法,n&#39;&amp;lt,calcT,int calcT,int n

閲覧数:
51
回答数:
1

違反報告

ベストアンサーに選ばれた回答

tekitoukさん

2019/8/1019:33:09

/*

貪欲法では条件によっては正しい解が出るとは限りません。
なので動的計画法で求めます。

(1)
if (m - C[n - 1] >= 0) {
T[n,m] = min(T[n - 1,m], T[n,m - C[n - 1]] + 1);
}
else {
T[n,m] = T[n - 1,m];
}

(2)
以下のソースコード

*/

#include <stdio.h>

#define MAX_m 364364

int min(int a, int b) {
if (a < b) { return a; }
else { return b; }
}

int T[5][MAX_m];
int C[4] = { 1,2,4,7 };

int calcT(int n, int m) {

int i, j;

for (i = 0; i <= n; i++) {
for (j = 0; j <= m; j++) {
T[i][j] = 1145141919;
}
}

T[0][0] = 0;

for (i = 1; i <= n; i++) {
for (j = 0; j <= m; j++) {
if (j - C[i - 1] >= 0) {
T[i][j] = min(T[i - 1][j], T[i][j - C[i - 1]] + 1);
}
else {
T[i][j] = T[i - 1][j];
}
}
}

return T[n][m];
}
int main() {

int n = 4;
int m = 810;

printf("%d\n", calcT(n, m));

return 0;
}

  • 質問者

    kar********さん

    2019/8/1204:16:16

    回答日:8/10
    T[i][j] = 1145141919;
    inm = 810;

    あっ・・・(察し)
    ありがとナス!
    --------------------------------------------------
    動的計画法
    独学ではなかなか初見の問題で対応できず困っておりました
    ありがとうございます

  • その他の返信(1件)を表示

返信を取り消しますが
よろしいですか?

  • 取り消す
  • キャンセル

この回答は投票によってベストアンサーに選ばれました!

この質問につけられたタグ

みんなで作る知恵袋 悩みや疑問、なんでも気軽にきいちゃおう!

Q&Aをキーワードで検索:

Yahoo! JAPANは、回答に記載された内容の信ぴょう性、正確性を保証しておりません。
お客様自身の責任と判断で、ご利用ください。
本文はここまでです このページの先頭へ

「追加する」ボタンを押してください。

閉じる

※知恵コレクションに追加された質問は選択されたID/ニックネームのMy知恵袋で確認できます。

不適切な投稿でないことを報告しました。

閉じる