c - 快速硬币兑换算法，C中最多可容纳3个硬币

我有贪心算法，它解决了硬币兑换问题的所有可能的解决方案硬币的最大金额是3。最少1。
例子
用硬币{1,2,3,4}我想求和10
所以程序输出
（4+4+2）
（3+3+4）
对于硬币{4，5，8，3}和12
（3+4+5）
（4+4+4）
（4+8）
等。
问题是我的算法效率很低，因为它涉及许多for循环。我搜索了很多，但只找到了算法，它只显示无限多硬币的解的数量或硬币的变化。
我的职责。硬币以前是按升序排列的。

void Count (int coins[], int cash, int n) {
    int or = 3; // Begin with a+b+c for or=2 its a+b, or=1 its a
    int i1,i2,i3;
    int sum;
    int result = 0;
    if (coins[0]*3 > cash) {
        or = 2;
    }
    if (coins[0]*2 < cash) {
        for (i1 = 0; i1<n; i1++) {
            if (or >= 2) {
                for (i2 = i1; i2<n; i2++) {
                    if (or==3) {
                        sum = coins[i1] + coins[i2];
                        for (i3=i2; i3<n; i3++) {
                            if (sum+coins[i3] == cash) {
                                printf("%d = %d + %d + %d\n", cash, coins[i1], coins[i2], coins[i3]);
                                result++;
                                break;
                            } else if (sum+coins[i3] > cash) {
                                if (i3==i2 && i2==i1) {
                                    or--;
                                    i2 = -1;
                                    i1 = 0;
                                } else if (i3==i2) {
                                    i2 = n;
                                }
                                break;
                            }
                        }
                    } else {
                        sum = (coins[i1] + coins[i2]);
                        if (sum == cash) {
                            printf("%d = %d + %d\n", cash, coins[i1], coins[i2]);
                            result++;
                        } else if (sum > cash) {
                            if (i2==i1) {
                                or--;
                                i1 = -1;
                            }
                            break;
                        }
                    }
                }
            } else {
                break;
            }
        }
    }
    int o;
    if (coins[0]<=cash && coins[n-1] >= cash) {
        for (o=0;o<n;o++) {
            if (coins[o]==cash) {
                printf("%d = %d\n", cash, coins[o]);
                result++;
                break;
            }
        }
    }
    printf("Result: %d\n", result);
}

最佳答案

（摘自我用php写的另一篇so文章。）
可以使用堆栈枚举有效的组合。下面的版本使用了一个小的优化，计算是否需要最小的当前面额如果存在任何一个最少的组合组合，则可以返回一个以上的组合，这可以通过记忆化来限制；如果当前面额可以完成零变化的组合，则可以添加早期退出。我希望简洁的注释代码是自解释的（如果您想进一步解释，请告诉我）：

function leastChange($coin_value,$inventory,$price){
  $n = count($inventory);
  $have = 0;
  for ($i=0; $i<$n; $i++){
    $have += $inventory[$i] * $coin_value[$i];
  }

  $stack = [[0,$price,$have,[]]];
  $best = [-max($coin_value),[]];

  while (!empty($stack)){

    // each stack call traverses a different set of parameters
    $parameters = array_pop($stack);
    $i = $parameters[0];
    $owed = $parameters[1];
    $have = $parameters[2];
    $result = $parameters[3];

    // base case
    if ($owed <= 0){
      if ($owed > $best[0]){
        $best = [$owed,$result];
      } else if ($owed == $best[0]){

        // here you can add a test for a smaller number of coins

        $best[] = $result;
      }
      continue;
    }

    // skip if we have none of this coin
    if ($inventory[$i] == 0){
      $result[] = 0;
      $stack[] = [$i + 1,$owed,$have,$result];
      continue;
    }

    // minimum needed of this coin
    $need = $owed - $have + $inventory[$i] * $coin_value[$i];

    if ($need < 0){
      $min = 0;
    } else {
      $min = ceil($need / $coin_value[$i]);
    }

    // add to stack
    for ($j=$min; $j<=$inventory[$i]; $j++){
      $stack[] = [$i + 1,$owed - $j * $coin_value[$i],$have - $inventory[$i] * $coin_value[$i],array_merge($result,[$j])];
      if ($owed - $j * $coin_value[$i] < 0){
        break;
      }
    }
  }

  return $best;
}

输出：

$coin_value = [10,5,3,1];
$inventory = [0,1,3,4];
$price = 12;

echo json_encode(leastChange($coin_value,$inventory,$price)); // [0,[0,1,2,1],[0,1,1,4],[0,0,3,3]]

$coin_value = [10,5,3,1];
$inventory = [0,1,4,0];
$price = 12;

echo json_encode(leastChange($coin_value,$inventory,$price)); // [0,[0,0,4]]

$coin_value = [10,5,3,1];
$inventory = [0,1,3,0];
$price = 6;

echo json_encode(leastChange($coin_value,$inventory,$price)); // [0,[0,0,2]]

$coin_value = [10,5,3,1];
$inventory = [0,1,3,0];
$price = 7;

echo json_encode(leastChange($coin_value,$inventory,$price)); // [-1,[0,1,1]]

如果你也对最低数量的硬币感兴趣，我认为只有我们能保证更好的可能性不会被忽略，记忆才能起作用。我认为如果我们先用最大的硬币进行深度优先搜索，这是可以做到的。如果我们已经用更大的硬币得到了同样的数目，那就没有必要继续使用当前的线索。确保输入的库存是按面额大小降序排列的硬币，并添加/更改以下内容：

// maximum needed of this coin
$max = min($inventory[$i],ceil($owed / $inventory[$i]));

// add to stack
for ($j=$max; $j>=$min; $j--){

关于c - 快速硬币兑换算法，C中最多可容纳3个硬币，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/40947914/