硬貨の最小の枚数

[kano]

動的計画法で１５円の支払いを１、２、７、８、１２円玉で支払いたいと考えています。

最終的には　６　×　１５　の表で表示したいです。

アルゴリズムに関して全く分からない状態となっています。

アドバイスお願いします。

コード:

#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');
}

[かずま]

最終的には　６　×　１５　の表で表示したいです。

6 x 15 の表の意味が分かりません。
期待する結果表示を示してください。

アルゴリズムに関して全く分からない状態となっています。

アルゴリズムが分からなくても、次のような考え方を
するんだというのは分かっているんですよね。

コード:

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枚
...

アドバイスお願いします。

・コンパイルできるソースを提示してください。
・コンパイルできないならエラーメッセージをそのまま貼り付けてください。


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

分からないところは質問してください。
質問を放置しないでください。
複数の投稿には同じ名前を使ってください。
フォーラム(掲示板)ルールに従ってください。

[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');
}

[かずま]

表のイメージは
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++ でコンパイルしたんですが、実行するたびに変な値が異なります。
件名にある「硬貨の最小の枚数」は表示しないのですか？

とても参考になりました。ありがとうございます。

参考になったということは、内容が理解できたということですか？
「分からないところは質問してください。」と申し上げたのに、
質問がないのは、理解できたということですか？

[かずま]

これなら分かりますか？

総当たりによる解

コード:

#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);
}