c - C中最多3个硬币的快速硬币找零算法

Question

我有贪心算法，它解决了硬币找零问题的所有可能解。硬币的最大数量是 3。最小 1。示例

With coins {1,2,3,4} I want to make sum 10 So the program outputs

• (4+4+2)
• (3+3+4)

For coins {4, 5, 8, 3} and sum 12 it's

• (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);
}

Answer 1

(来 self 用 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--){