お金の両替問題の各種延伸問題
特定の価格を作ることができるか（お金の両替問題）
-
int price [5] = {5, 2, 6, 11, 17}; // 各種面額、順序は自由。
-
bool c[1000+1];
-
// {5, 2, 6, 11, 17} の面額で価格 m を作れるか確認する
-
void change(int m)
-
{
-
memset(c, false, sizeof(c));
-
c[0] = true;
-
for (int i = 0; i < 5; ++i) // 各種面額を順に追加
-
for (int j = price [i]; j <= m; ++j) // 低価格から高価格へ
-
c [j] ||= c [j-price [i]]; // 作れる、作れる、作れる
-
if (c[m])
-
cout << "作れる";
-
else
-
cout << "作れない";
-
}
-
int price[5] = {5, 2, 6, 11, 17};
-
int c [5][1000+1]; // 0 以上は計算済み、-1 は未計算。
-
// 最初はすべて - 1 で初期化する必要がある。
-
void change(int n, int m)
-
{
-
if (n < 0 || m < 0) return 0; // 0 は false を意味する
-
if (m == 0) return 1; // 1 は true を意味する
-
if (c[n][m] != -1) return c[n][m];
-
return c[n][m] = change(n-1, m) | change(n, m - price[n]);
-
}
特定の価格を作る方法は何通りか（コイン変更問題）
-
int price[5] = {5, 2, 6, 11, 17};
-
int c[1000+1];
-
void change(int m)
-
{
-
memset(c, 0, sizeof(c));
-
c[0] = 1;
-
for (int i = 0; i < 5; ++i)
-
for (int j = price[i]; j <= m; ++j)
-
c[j] += c[j-price[i]];
-
cout << "価格" << m << "を作る方法は" << c [m] << "通り";
-
}
特定の価格を作るための最小コイン数（コイン作成問題）
-
int price[5] = {5, 2, 6, 11, 17};
-
int c[1000+1];
-
void change(int m)
-
{
-
memset(c, 0x7f, sizeof(c));
-
c[0] = 0;
-
for (int i = 0; i < 5; ++i)
-
for (int j = price[i]; j <= m; ++j)
-
c[j] = min(c[j], c[j-price[i]] + 1);
-
cout << "価格" << m;
-
cout << "最小で（のみ）" << c [m] << "枚のコインが必要";
-
}
特定の価格を作るためのコインの使用量、どのような可能性があるか。
-
int price[5] = {5, 2, 6, 11, 17};
-
long long c [1000]; // 各セルは 1 つのビットセット、
-
// その価格を作るために使用できるコインの数を記録し、さまざまな可能性を含む。
-
void change(int m)
-
{
-
memset(c, 0, sizeof(c));
-
c[0] = 1;
-
for (int i = 0; i < 5; ++i)
-
for (int j = price[i]; j <= m; ++j)
-
// コインの数を 1 増やし、各可能性を 1 増やす。
-
c[j] |= c[j-price[i]] << 1;
-
for (int i = 1; i <= 63; ++i)
-
if (c[m] & (1 << i))
-
cout << "コイン" << i << "枚で価格" << m "を作ることができる";
-
}
特定の価格を作ることができるか、ただしコインの供給に制限がある。
-
int price[5] = {5, 2, 6, 11, 17};
-
int num [5] = {4, 5, 5, 3, 2}; // 各種面額の供給量
-
bool c[1000+1];
-
void change(int m)
-
{
-
memset(c, 0, sizeof(c));
-
c[0] = true;
-
for (int i = 0; i < 5; ++i)
-
for (int k = 0; k < M [i]; ++k) // 各種余数を分けて処理
-
// for (int k = 1; k <= M [i]; ++k) // 少し早い書き方
-
{
-
int left = T[i];
-
for (int j = k; j <= m; j += M [i]) // 低価格から高価格へ
-
// 0 種類から i 種類の面額で作れる場合、コインを節約できる。
-
if (c[j])
-
{
-
left = T [i]; // 弾薬を補充
-
}
-
// 過去に作れなかった場合、現在の面額を使って作る必要がある。
-
else if (left > 0)
-
{
-
left--; // コインを 1 枚使用
-
c[j] = true;
-
}
-
}
-
if (c[m])
-
cout << "作れる";
-
else
-
cout << "作れない";
-
}