#5
by かずま » 5年前
これなら分かりますか?
総当たりによる解
コード:
#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);
}
これなら分かりますか?
総当たりによる解
[code]
#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);
}
[/code]
他の硬貨を何枚使ったかにかかわらず、
2 x 2 x 3 x 8 x 16 通り全部について
15円になるかどうか調べています。
動的計画法による解
[code]
#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);
}
[/code]
既に使った硬貨の枚数にしたがって、
使う硬貨の最大枚数が動的に変化します。
動的計画法による解を再帰呼出しを使って書き直したもの
[code]
#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);
}
[/code]