ページ 1 / 1
硬貨の最小の枚数
Posted: 2019年1月30日(水) 01:28
by kano
動的計画法で15円の支払いを1、2、7、8、12円玉で支払いたいと考えています。
最終的には 6 × 15 の表で表示したいです。
アルゴリズムに関して全く分からない状態となっています。
アドバイスお願いします。
コード:
#include <stdio.h>
#define N 5 + 1 //表の硬貨の数
#define M 15 + 1 //表の支払いの代金
void Func(int m);
void print_matrix(int a[][N]);
void print_array(const int *a);
//==============================================================
// メイン関数
//==============================================================
int main(void) {
const int m = 15; // 支払金額
Func(m);
return 0;
}
//==============================================================
// 金額 m 円の支払いに必要な紙幣および硬貨の枚数を表示する
//==============================================================
void Func(int m) {
int c[] = { 1,2,7,8,12 }; // 支払いに使用する紙幣および硬貨
int a[] = { 12,8,7,2,1 }; // 支払いに使用する紙幣および硬貨
const int loop = sizeof(a) / sizeof(int); // ループ回数
int i,j,k; // ループ用
int counter[M][N];
int count[N - 1];
// 答えが正しいかどうかの確認用
for (i = 0; i < loop; i++) {
if (m / a[i] > 0) {
printf("[%5d] : %d\n", a[i], m / a[i]); // 枚数を表示する
}
m %= a[i]; // c[i] 円で支払ったあとの残りの支払金額を求める
}
printf("\n");
//表の初期化
for (i = 0; i < N ; i++) {
for (j = 0; j < M ;j++){
if (i == 0) { counter[j][i] = j; }
else counter[j][i] = 0;
}
}
counter[0][0] = 0; counter[0][1] = c[0]; counter[0][2] = c[1];
counter[0][3] = c[2]; counter[0][4] = c[3]; counter[0][5] = c[4];
for(i = 0;i < N - 1;i++) count[i] = { 0 };
for (i = 0; i < N; i++) {
for (i = 0; i < N; i++) {
for (j = 0; j < M; j++) {
if (counter[i][j] - counter[i][0] == 0) {
}
}
}
print_matrix(counter);
print_array(count);
printf("\n");
}
//行列を表示する関数
void print_matrix(int a[][N])
{
int i, j;
for (i = 0; i<N; i++) {
for (j = 0; j<M; j++) {
printf("%3d ", a[j][i]);
}
printf("\n");
}
return;
}
void print_array(const int *a)
{
for (int i = 0; i < N - 1; i++) printf("%3d ", a[i]);
putchar('\n');
}
Re: 硬貨の最小の枚数
Posted: 2019年1月30日(水) 10:52
by かずま
kano さんが書きました: ↑5年前
最終的には 6 × 15 の表で表示したいです。
6 x 15 の表の意味が分かりません。
期待する結果表示を示してください。
kano さんが書きました: ↑5年前
アルゴリズムに関して全く分からない状態となっています。
アルゴリズムが分からなくても、次のような考え方を
するんだというのは分かっているんですよね。
コード:
12 x 1 + 2 x 1 + 1 x 1 = 15 3枚
12 x 1 + 1 x 3 = 15 4枚
8 x 1 + 7 x 1 = 15 2枚
...
kano さんが書きました: ↑5年前
アドバイスお願いします。
・コンパイルできるソースを提示してください。
・コンパイルできないならエラーメッセージをそのまま貼り付けてください。
6 x 15 の表の意味が分からないので、期待通りの結果を表示しませんが、
参考になるかもしれないので、次のようなプログラムを書いてみました。
コード:
#include <stdio.h>
#define N 5 // 硬貨の種別の数
#define M 15 // 合計金額
int coin[N] = { 12, 8, 7, 2, 1 }; // 硬貨の種別
int count[N]; // 各硬貨の枚数
int total; // 計算途中の合計金額
int minval = 9999; // 硬貨の合計枚数の最小値
void print(void)
{
int sum = 0;
for (int i = 0; i < N; i++) printf("%3d ", count[i]), sum += count[i];
printf(" %3d\n", sum);
if (sum < minval) minval = sum;
}
void Func(int m, int i)
{
if (i < N)
for (int k = m / coin[i]; k >= 0; k--) {
int s = coin[i] * k;
count[i] = k;
total += s;
Func(m - s, i + 1);
total -= s;
}
else
if (total == M) print();
}
int main(void)
{
for (int i = 0; i < N; i++) printf("%3d ", coin[i]);
puts(" 枚数");
for (int i = 0; i < N; i++) printf("----");
puts("-------");
Func(M, 0);
printf("\n最小枚数は %d\n", minval);
}
実行結果
コード:
12 8 7 2 1 枚数
---------------------------
1 0 0 1 1 3
1 0 0 0 3 4
0 1 1 0 0 2
0 1 0 3 1 5
0 1 0 2 3 6
0 1 0 1 5 7
0 1 0 0 7 8
0 0 2 0 1 3
0 0 1 4 0 5
0 0 1 3 2 6
0 0 1 2 4 7
0 0 1 1 6 8
0 0 1 0 8 9
0 0 0 7 1 8
0 0 0 6 3 9
0 0 0 5 5 10
0 0 0 4 7 11
0 0 0 3 9 12
0 0 0 2 11 13
0 0 0 1 13 14
0 0 0 0 15 15
最小枚数は 2
分からないところは質問してください。
質問を放置しないでください。
複数の投稿には同じ名前を使ってください。
フォーラム(掲示板)ルールに従ってください。
Re: 硬貨の最小の枚数
Posted: 2019年1月30日(水) 14:16
by kano
表のイメージは
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
7 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
8 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
12 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
とても参考になりました。ありがとうございます。
コード:
#include <stdio.h>
#define N 5 + 1 //表の硬貨の数
#define M 15 + 1 //表の支払いの代金
void Func(int m);
void print_matrix(int a[][N]);
void print_array(const int *a);
//==============================================================
// メイン関数
//==============================================================
int main(void) {
const int m = 15; // 支払金額
Func(m);
return 0;
}
//==============================================================
// 金額 m 円の支払いに必要な紙幣および硬貨の枚数を表示する
//==============================================================
void Func(int m) {
int c[] = { 1,2,7,8,12 }; // 支払いに使用する紙幣および硬貨
int a[] = { 12,8,7,2,1 }; // 支払いに使用する紙幣および硬貨
const int loop = sizeof(a) / sizeof(int); // ループ回数
int i,j,k,temp; // ループ用
int counter[M][N];
int count[N];
// 答えが正しいかどうかの確認用
for (i = 0; i < loop; i++) {
if (m / a[i] > 0) {
printf("[%5d] : %d\n", a[i], m / a[i]); // 枚数を表示する
}
m %= a[i]; // c[i] 円で支払ったあとの残りの支払金額を求める
}
printf("\n");
//表の初期化
counter[0][0] = 0; counter[0][1] = c[0]; counter[0][2] = c[1];
counter[0][3] = c[2]; counter[0][4] = c[3]; counter[0][5] = c[4]; temp = 1;
for(i = 0;i < N;i++){count[i] = 0 ;}
for (i = 0; i < N ; i++) {
for (j = 1; j < M ;j++){
if(i == 0 || i == 1){counter[j][i] = j;}
else if(i >= 2 && (j - counter[0][i]) < 0){
counter[j][i] = counter[j][i-1];
}
else if(i >= 2 && (j - counter[0][i] == 0)){
count[i]++;
if(count[i] < counter[j][i-1]){
counter[j][i] = 1;
}
else if(i >= 2 && (j - counter[0][i] > 0)){
}
}
else {
counter[j][i] = 0;
}
}
temp = 0;
}
// printf("%d\n",counter[2][1] - counter[2][1]);
// printf("%d\n",2 - counter[0][2]);
print_matrix(counter);
printf("\n");
print_array(count);
printf("\n");
}
//行列を表示する
void print_matrix(int a[][N])
{
int i, j;
for (i = 0; i<N; i++) {
for (j = 0; j<M; j++) {
printf("%3d ", a[j][i]);
}
printf("\n");
}
return;
}
void print_array(const int *a)
{
int i;
for (i = 0; i < N; i++){ printf("%3d ", a[i]);}
putchar('\n');
}
Re: 硬貨の最小の枚数
Posted: 2019年1月30日(水) 19:16
by かずま
kano さんが書きました: ↑5年前
表のイメージは
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
7 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
8 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
12 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
この表の各要素の意味を説明してください。
1列目は、硬貨の種別ですね。
2列目が全部 1 ですが、これは何ですか?
2行目は 1円玉の使用枚数で 1, 2, ..., 15 となっているのですか?
3行3列目以降がすべて 0 でいいんですか?
本当にこれが期待する結果なんですか?
プログラムを読んでも、何をやっているのかわかりません。
コンパイルはできましたが、実行すると次のように
わけの分からない結果になりました。
コード:
[ 12] : 1
[ 2] : 1
[ 1] : 1
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
2 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0
7 1 1 0 0 0 0 671 0 0 0 0 0 0 0 0
8 1 1 0 0 0 0 671 7339360 0 0 0 0 0 0 0
12 1 1 0 0 0 0 671 7339360 0 0 0 197068 0 0 0
0 0 1 1 1 1
VC++ でコンパイルしたんですが、実行するたびに変な値が異なります。
件名にある「硬貨の最小の枚数」は表示しないのですか?
kano さんが書きました: ↑5年前
とても参考になりました。ありがとうございます。
参考になったということは、内容が理解できたということですか?
「分からないところは質問してください。」と申し上げたのに、
質問がないのは、理解できたということですか?
Re: 硬貨の最小の枚数
Posted: 2019年2月01日(金) 15:31
by かずま
これなら分かりますか?
総当たりによる解
コード:
#include <stdio.h>
int main(void)
{
int mv = 15; // 硬貨の合計枚数の最小値(minimum value) 暫定値15
puts(" 12 8 7 2 1 枚数\n"
"---------------------------");
for (int a = 15 / 12; a >=0; a--) // 12円玉の使用枚数は最大 1枚
for (int b = 15 / 8; b >=0; b--) // 8円玉の使用枚数は最大 1枚
for (int c = 15 / 7; c >=0; c--) // 7円玉の使用枚数は最大 2枚
for (int d = 15 / 2; d >=0; d--) // 2円玉の使用枚数は最大 7枚
for (int e = 15 / 1; e >=0; e--) // 1円玉の使用枚数は最大 15枚
if (12*a + 8*b + 7*c + 2*d + 1*e == 15) {
int n = a + b + c + d + e; // 硬貨の合計枚数(number)
printf("%3d %3d %3d %3d %3d %5d\n", a, b, c, d, e, n);
if (n < mv) mv = n; // 最小値の更新
}
printf("\n最小枚数は %d\n", mv);
}
他の硬貨を何枚使ったかにかかわらず、
2 x 2 x 3 x 8 x 16 通り全部について
15円になるかどうか調べています。
動的計画法による解
コード:
#include <stdio.h>
int main(void)
{
int mv = 15; // 硬貨の合計枚数の最小値(minimum value) 暫定値 15
puts(" 12 8 7 2 1 枚数\n"
"---------------------------");
int m1 = 15;
for (int a = m1 / 12; a >=0; a--) { // a は 12円玉の使用枚数
int m2 = m1 - 12*a; // m2 は 12円玉使用後の残り金額
for (int b = m2 / 8; b >=0; b--) { // b は 8円玉の使用枚数
int m3 = m2 - 8*b; // m3 は 8円玉使用後の残り金額
for (int c = m3 / 7; c >=0; c--) { // c は 7円玉の使用枚数
int m4 = m3 - 7*c; // m4 は 7円玉使用後の残り金額
for (int d = m4 / 2; d >=0; d--) { // d は 2円玉の使用枚数
int m5 = m4 - 2*d; // m5 は 2円玉使用後の残り金額
int e = m5 / 1; // e は 1円玉の使用枚数
int n = a + b + c + d + e; // 硬貨の合計枚数(number)
printf("%3d %3d %3d %3d %3d %5d\n", a, b, c, d, e, n);
if (n < mv) mv = n; // 最小値の更新
}
}
}
}
printf("\n最小枚数は %d\n", mv);
}
既に使った硬貨の枚数にしたがって、
使う硬貨の最大枚数が動的に変化します。
動的計画法による解を再帰呼出しを使って書き直したもの
コード:
#include <stdio.h>
#define N 5
#define M 15
int t[N] = { 12, 8, 7, 2, 1 }; // 硬貨の種別(type)
int c[N]; // 各硬貨の枚数(count)
int mv = M; // 硬貨の合計枚数の最小値(minimum value)
void step(int m, int i) // m円を i番目以降の硬貨で支払う
{
if (m == 0) {
int k = 0;
for (i = 0; i < N; i++) printf("%3d ", c[i]), k += c[i];
printf("%5d\n", k);
if (k < mv) mv = k;
}
else if (i < N-1) // 1円玉以外の場合
for (int k = m / t[i]; k >= 0; k--)
c[i] = k, step(m - t[i]*k, i+1);
else // 1円玉の場合 for文は不要
c[i] = m, step(0, N), c[i] = 0;
}
int main(void)
{
for (int i = 0; i < N; i++) printf("%3d ", t[i]);
puts(" 枚数");
for (int i = 0; i < N; i++) printf("----");
puts("-------");
step(M, 0);
printf("\n最小枚数は %d\n", mv);
}