C语言 如何找到给定目标金额所需的最小硬币数量(与现有硬币不同)

Question

这是一个经典问题，其中coins[]中给出了一个硬币数量列表，len=coins[]数组的长度，我们试图找到获得target所需的最小硬币数量。

硬币数组按升序排序

注意:我正在尝试优化效率。显然，我可以在硬币数组中运行一个for循环，并将target%coins[i]加在一起，但当我有coins[] = {1,3,4}和target = 6时，这将是错误的，for循环方法将给出3，即1,1,4，但最优解是2，即3,3。

我还没学过矩阵和多维数组，有没有办法不用它们来解决这个问题?我写了一个函数，但它似乎在一个无限循环中运行。

int find_min(const int coins[], int len, int target) {
int i;
int min = target;
int curr;
for (i = 0; i < len; i++) {
if (target == 0) {
return 0;
}
if (coins[i] <= target) {
curr = 1 + find_min(coins, len, target - coins[i]);
if (curr < min) {
min = curr;
}
}
}
return min;
}

Answer 1

我可以建议你阅读，

https://www.geeksforgeeks.org/generate-a-combination-of-minimum-coins-that-results-to-a-given-value/

唯一的事情是没有C版本的代码，但如果真的需要它，你可以自己做移植。

Answer 2

既然没有人给出一个好的答案，我自己想出来的。我不妨贴个答案。

我添加了一个名为lp的数组，它在main中初始化，

int lp[4096];
int i;
for (i = 0; i <= COINS_MAX_TARGET; i++) {
lp[i] = -1;
}

lp的每一个索引都等于-1。

int find_min(int tar, const int coins[], int len, int lp[])
{
// Base case
if (tar == 0) {
lp[0] = 0;
return 0;
}
if (lp[tar] != -1) {
return lp[tar];
}
// Initialize result
int result = COINS_MAX_TARGET;
// Try every coin that is smaller than tar
for (int i = 0; i < len; i++) {
if (coins[i] <= tar) {
int x  = find_min(tar - coins[i], coins, len, lp);
if (x != COINS_MAX_TARGET)
result = ((result > (1 + x)) ? (1+x) : result);
}
}
lp[tar] = result;
return result;
}