您可以使用堆棧來枚舉有效組合。以下版本使用一個小的優化，計算是否需要當前面額的最小值。如果存在任何可能會被記憶化限制的變化組合，則返回多於一個的最小變化組合;如果當前面額能夠以零變化完成組合，則還可以增加提前退出。我希望扼要地註釋代碼是不言自明的（讓我知道，如果你想進一步的解釋）：
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]]
更新：
既然你也有興趣在最低的號碼硬幣，我認爲memoization只能工作，如果我們能保證更好的可能性不會被跳過。如果我們先用最大的硬幣進行我們的深度優先搜索，我認爲可以做到這一點。如果我們已經使用較大的硬幣達到相同的金額，則繼續當前線程沒有意義。使降面額大小的順序排序確定輸入庫存呈現硬幣，並添加/更改如下：
// maximum needed of this coin
$max = min($inventory[$i],ceil($owed/$inventory[$i]));
// add to stack
for ($j=$max; $j>=$min; $j--){
我想只是使用簡單的動態編程是好的 – throwit
嗯，我試圖解決這個問題，因爲它看起來很有趣。我寫了一個算法，應該爲你工作，因爲我不想安裝PHP服務器，我做了它在JS。你可以將其轉換爲PHP。讓我知道如果它確定。我可以給你的代碼。 –
@HarryBomrah，是的，絕對會有很大的幫助。 – kojow7