これはあなたのために働くはずです：
このコードは何をしますか (関数getKnapsackSum())?
1.データを準備する
関数の最初の数行でデータを準備します。つまり、配列 DESC を でソートしrsort()ます。でリストの最後の要素を取得しend()、配列ポインタをリセットrest()して一時変数に割り当てます。
2.入力チェック
合計の計算を開始する前に、入力が 0 でないことを確認します。
3.合計を計算する
この後、本当のことが起こります (IT ブードゥー教、そうではありません)! 合計が得られない限り、false であるループから始めます。while ループの次の 2 行は、最初に合計を計算できない場合は 0 を含む配列を返すことを確認し、次に、配列ポインターの「オフセット」を取得したときに設定したことを確認します。最後の配列要素に戻ります。
次に、最初の if 句があり、間違いがあったかどうかを確認し、より低い値で試行する必要があります。例として：
list = [3, 5, 6]
sum = 8
//entire sum
| 0
|
check 6: |
|
6 + sum -> 8 | 6 | fits
6 + sum -> 8 | | does not fit
|
check 5: |
|
5 + sum -> 8 | | does not fit
|
check 3: |
|
3 + sum -> 8 | | does not fit
--------------------------------------------------------
= sum = [6] != 8
この例でわかるように、アルゴリズムは 6 で合計を作成し始めたため、間違いを犯しましたが、その後は最後まで作成できませんでした。配列ポインターの現在の要素は配列の末尾であり、この値 + 現在の合計は目標よりも高くなります。
この場合、合計配列から最後の値を削除し、リストの最上位の要素を取り出します。そのため、次のデータを使用して再試行します。
list = [3, 5]
//^ As you can see it removed the highest value of the list
sum = 8
//entire sum
| 0 <- it removed the last value of the sum array, here 6
|
check 5: |
|
5 + sum -> 8 | 5 | fits
5 + sum -> 8 | | does not fit
|
check 3: |
|
3 + sum -> 8 | 3 | fits
3 + sum -> 8 | | does not fit
--------------------------------------------------------
= sum = [5, 3] == 8
ご覧のとおり、最初の if 句により、リストを使用して合計を作成できました。そのため、if ステートメントは、レベル 1 のエラーを確実に修正します。
while ループの 2 番目の if ステートメントは、レベル 2 のエラーを修正します。では、レベル 2 のエラーとは何でしょうか? また、例をもう一度見てみましょう。
list = [3, 5, 6]
sum = 22
//entire sum
| 0
|
check 6: |
|
6 + sum -> 22 | 6 | fits
6 + sum -> 22 | 6 | fits
6 + sum -> 22 | 6 | fits
6 + sum -> 22 | | does not fit
|
check 5: |
|
5 + sum -> 22 | | does not fit
|
check 3: |
|
3 + sum -> 22 | 3 | fits
3 + sum -> 22 | | does not fit
--------------------------------------------------------
= sum = [6, 6, 6, 3] != 22
ご覧のとおり、合計を完全に構築することはできませんでした。ただし、今回はレベル 1 のエラーではありません。現在の合計から最後の要素を削除し、最上位の要素を削除した新しいリストを調べても、ここでわかるようにまだ合計を作成できないためです。 :
エラーの修正レベル 1:
list = [3, 5]
//^ As you can see it removed the highest value of the list
sum = 22
//entire sum
| [6, 6, 6] <- it removed the last value of the sum array, here 3
|
check 5: |
|
5 + sum -> 22 | | does not fit
|
check 3: |
|
3 + sum -> 22 | 3 | fits
3 + sum -> 22 | | does not fit
|
--------------------------------------------------------
= sum = [6, 6, 6, 3] != 22
ご覧のとおり、スタックしていることがわかりますが、最初の if 句だけでは間違いを修正できません。そして、ここで 2 番目の if ステートメントがリストが空かどうかをチェックします。この場合は、すべての値を試したことを意味しますが、間違いは sum 配列の上位にあります。
したがって、合計配列の配列要素を 1 つ戻して削除します。また、間違いであった番号のないリストを取得するために、間違いをオフセットとして取得します。ここで[6, 6, 6, 3]は、最初の if 句から 3 が削除されるため、配列は次のようになります[6, 6, 6]。2 番目の if ステートメントは、間違いが 6 だったことを確認します。それを削除し、数字を選択するリストを修正します。
結果の配列は次のよう[6, 6]になり、数値を選択するリストは次のようになります[5, 3]。そして、レベル 2 の修正を行ったので、以下に示すように合計を作成できます。
list = [3, 5]
//^ As you can see it removed the highest value of the list
sum = 22
//entire sum
| [6, 6] <- it removed the last value of the sum array, here 3 and 6
|
check 5: |
|
5 + sum -> 22 | 5 | fits
5 + sum -> 22 | 5 | fits
5 + sum -> 22 | | does not fit
|
check 3: |
|
3 + sum -> 22 | | does not fit
|
|
--------------------------------------------------------
= sum = [6, 6, 5, 5] == 22
したがって、この後、リストの現在の値が合計配列に収まり、目標よりも大きくないかどうかを確認するためだけに if else ステートメントがあります。収まる場合は配列に追加し、そうでない場合は次のリスト要素に移動します。
ご覧のとおり、私のコードはいくつかのエラーを修正していますが、それがすべてで機能することを 100% 確信しているわけではなく、sum 配列に戻る必要があるレベル 3 のエラーを生成できるかどうかもわかりません正しい 3 つの値があり、1 つある場合、コードがそれを修正するかどうか、または無限ループに陥るかどうかもわかりません。
しかし、ここで話していることはすべて、すべての魔法を行うコードです。
<?php
//data
$arr = [3,5,6,10,15,30];
$sum = 69;
//get sum
function getKnapsackSum($arr, $sum) {
//prepare data
rsort($arr);
$end = end($arr);
reset($arr);
$tmp = $arr;
$result = [];
//check if it is not a empty input
if($sum == 0 || empty($tmp) || array_sum($tmp) == 0) return [0];
//calculate the sum
while(array_sum($result) != $sum) {
if(empty($tmp) && empty($result)) return [0];
if(current($tmp) === FALSE) end($tmp);
//correction for errors level 1
if(current($tmp) == $end && array_sum($result) + current($tmp) > $sum) {
array_pop($result);
array_shift($tmp);
reset($tmp);
}
//correction for errors level 2
if(empty($tmp)) {
$mistake = array_pop($result);
if($mistake == NULL) return [0];
$tmp = array_slice($arr, array_search($mistake, $arr)+1);
reset($tmp);
}
if(array_sum($result) + current($tmp) <= $sum)
$result[] = current($tmp);
else
next($tmp);
}
return $result;
}
$result = getKnapsackSum($arr, $sum);
print_r($result);
?>
出力：
Array ( [0] => 30 [1] => 30 [2] => 6 [3] => 3 )
また、入力のいくつかの例と、コードからの出力があります。
input | output
------------------------------------
list: [] |
goal: 0 | sum: [0]
------------------------------------
list: [] |
goal: 1 | sum: [0]
------------------------------------
list: [0] |
goal: 1 | sum: [0]
------------------------------------
list: [0] |
goal: 0 | sum: [0]
------------------------------------
list: [3, 5, 6] | //error level 1
goal: 8 | sum: [5, 3]
------------------------------------
list: [3, 5, 6] | //error level 2
goal: 22 | sum: [6, 6, 5, 5]
------------------------------------
list: [5, 7, 9] | //can't build the sum
goal: 56 | sum: [0]
------------------------------------
list: [5, 7, 9] |
goal: 34 | sum: [9, 9, 9, 7]
------------------------------------