快速硬幣更換算法最多3個硬幣在C

Question

我有貪婪算法，它解決了硬幣更換問題的所有可能的解決方案。硬幣的最大數量爲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）

等

問題是，我的算法效率非常低，因爲它涉及很多週期。我搜索了很多，但只找到算法，只顯示無數個硬幣的解決方案或硬幣變化的數量。

我的功能。硬幣按照升序排列。

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

（從另一個SO後我寫的，在PHP）

您可以使用堆棧來枚舉有效組合。以下版本使用一個小的優化，計算是否需要當前面額的最小值。如果存在任何可能會被記憶化限制的變化組合，則返回多於一個的最小變化組合;如果當前面額能夠以零變化完成組合，則還可以增加提前退出。我希望扼要地註釋代碼是不言自明的（讓我知道，如果你想進一步的解釋）：

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--){