可以用DP 方法去解:
coins_count[x], 表示已知x元, 可以最少用 coins_count[x] 个硬币来凑出来。
coins_count[x] = min{ coins_count[x - 1] + 1, coins_count[x - 3] + 1, coins_count[x - 5] + 1}
coins_count[11] 表示的数目的等于 : coins_count[10] , coins_count[8], coins_count[6] 中的最小值, 加 1。 比如 coins_count[8] 最小, 说明 8 元 最少需要 coins_count[8] 个硬币能凑出来, 在这个基础上添加一个面值 3 元的硬币, 就得到了 11 元。
//
// 使用若干个面值分别为 values[0..length] 的硬币 (可以重复, 并且 values[] 从小到大排序外币),
// 凑齐 Sum 元, 最少需要多少个硬币.
void find_least_coins(const int values[], const int length, const int Sum)
{
int * coins_count = new int[Sum + 1]; // coins_count[Sum] 表示, Sum 元可以用 coins_count[Sum] 个硬币凑出来.
int * coins_trace = new int[Sum + 1]; // coins_trace[Sum] 表示, 在 coins_trace[Sum] 的基础上, 加上一个硬币, 凑齐了Sum元.
// eg: coins_trace[11] = 6, 表示在 6 元的基础上增加了一个硬币凑到了 11 元.
// eg: coins_trace[5] = 0, 表示在 0 元的基础上增加了一个硬币凑到了 5 元, 即直接使用面值 5 元的硬币.
for (int i = 0; i < values[0]; i++) // 不能凑出比硬币最小面值还小的数额.
{
coins_count[i] = 0;
coins_trace[i] = -1; // 表示无意义.
}
for (int i = values[0]; i < Sum + 1; i++) // i 表示面额.
{
int min = i; // 最少使用硬币个数.
int idx = 0;
for (int j = 0; j < length; j++) // j 表示硬币面值数组的索引.
{
if (i == values[j]) // 面额 i 元可以用硬币 j 凑出, 则直接用硬币 j 搞定.
{
min = 1; // 表示最少使用 1 个硬币就搞定.
idx = 0; // 不用借助其他硬币
break;
}
else if (i > values[j]) // 面额 i 大于硬币 j 的面值
{
if (min >= coins_count[i - values[j]] + 1)
{
// eg : coins_count[11] = coins_count[8] + 1 (面值5的硬币)
min = coins_count[i - values[j]] + 1;
idx = i - values[j];
}
}
}
coins_count[i] = min;
coins_trace[i] = idx;
}
//
// 输出
// 输出组成 Sum 的硬币的个数
int count = coins_count[Sum];
cout << "total : " << count << endl;
// 输出组成 Sum 的硬币的面值
int i = Sum;
for (int c = 0; c < count; c++)
{
cout << "coin[" << i - coins_trace[i] << "] ";
i = coins_trace[i];
}
cout << endl;
}
void find_least_coins()
{
int values[] = { 1, 3, 5 };
find_least_coins(values, 3, 11);
}
原文链接: https://www.cnblogs.com/happylong/p/4506042.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/216205
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!