c - 递归函数构建

Question

我正在尝试编写一个函数，探索以数组形式给出的所有可能的数字组合，希望找到加起来达到一定数量的最小数字组，该数字作为参数传递。

这是我一直在做的事情，这似乎适用于某些情况，但并非所有情况；

我选择一个数字，从总和中减去它，然后将新的总和传递给函数，数组的限制完好无损，这使我可以选择重新选择数字，
在第二次调用中，我传递了新的总和，即总和减去当前选择的数字，但我将数组缩小了 1，这意味着我不会再次选择相同的数字。

但是，我意识到我没有涵盖所有选择，因为无论如何我假设任何数字对于解决方案都至关重要，但我不知道要传递哪些参数才能涵盖第三个选项，不选择数字，意味着不从总和中减去，并缩小数组的大小。

非常感谢您的帮助，顺便说一句，我正在用 C 语言编写。

    int howManyCoins(int*coins,int size,int sum)
{
    return howManyCoins_aux(coins,size,sum,size-1);
}

int howManyCoins_aux(int*coins,int size, int sum,int chosen)
{
    if (sum==0)return 1;
    if (sum<0)return 0;
    if (chosen==0) return 0;
    if (coins[chosen]>sum) return 0;
    int res1=0,res2=0,best_solution=0;
    for (int i=chosen;i>=0;i--)
    {
        res1+=howManyCoins_aux(coins,size,sum-coins[i],chosen);
        res2+=howManyCoins_aux(coins,size,sum-coins[i],chosen-1);
        if(!(res1+res2)) best_solution=0;
        else if (res1==0) best_solution=res2;
        else if (res2==0) best_solution=res1;
        else best_solution=res2>res1?res1:res2;
    }
    return best_solution;
}

Answer 1

您可以将您的选择简化为:选择硬币并能够重新选择硬币或不选择硬币(递归将覆盖所有选项)

替换:

res1+=howManyCoins_aux(coins,size,sum-coins[i],chosen);
res2+=howManyCoins_aux(coins,size,sum-coins[i],chosen-1);

与

res1 = howManyCoins_aux(coins, size, sum-coins[i], chosen);
res2 = howManyCoins_aux(coins, size, sum, chosen-1);

如果每种硬币只能选择 1 个:(即 change-making problem )

res1 = howManyCoins_aux(coins, size, sum-coins[i], chosen-1);
res2 = howManyCoins_aux(coins, size, sum, chosen-1);

你的算法有点不清楚，而且我认为有很多重复。您可以摆脱 for 循环，并将您的函数更改为:(未经测试)

int howManyCoins_aux(int *coins, int size, int sum, int chosen, int pos)
{
  if (sum == 0) return chosen;
  if (sum < 0 || pos == size) return 9999999;
  int res1 = 9999999;
  if (coins[pos] >= sum)
    res1 = howManyCoins_aux(coins, size, sum-coins[pos], chosen+1, pos);
  int res2 = howManyCoins_aux(coins, size, sum, chosen, pos+1);
  return min(res1, res2);
}

话虽这么说，递归可能不是可行的方法(即使在小型数据集上，它也会花费很长时间)。听起来像 integer programming 。链接中有一些解决该问题的选项。