PHP が動的プログラミングを使用して最適な赤い封筒の組み合わせを実現する方法の詳細な説明

                                                                                                               

現在、小さな要件に取り組んでいます。注文ごとに、ユーザーが使用できる赤い封筒の最大数が金額に基づいて決まります。ユーザーが赤い封筒の使用を選択した場合は、ユーザーが赤い封筒を選択できるようにする必要があります。所有する赤エンベロープのリストから最適な赤エンベロープの組み合わせを選択します。組み合わせた赤エンベロープの値は、使用できる赤エンベロープの最大値に最も近いか等しい必要があります。しばらく考えてみると、これは「0-1 ナップザック問題」ではないでしょうか? 以前学んだ「動的計画法」アルゴリズムをついに実践できるようになりました!

動的プログラミングとは

動的プログラミング（Dynamic programming、略称：DP）は、数学、経営科学、コンピュータサイエンス、経済学、生物学における手法です。元の問題を比較的単純な部分問題に分解することによって複雑な問題を解決するために情報学で使用される方法。

動的プログラミングは、重複する部分問題と最適な部分構造特性を持つ問題に適していることが多く、単純な解決策よりもはるかに時間がかかりません。

動的プログラミングに適用可能なシナリオ

動的プログラミングは、一般に、最適解を見つける問題を解決するために使用されます。問題を解決する過程では複数の決定が必要であり、各決定は一連の状態を生成し、最適な決定から次の決定が継続され、最終的に最適な結果が見つかります。

さらに、動的計画法には次の 3 つの特徴もあります。

最適な部分構造のプロパティ

問題の最適解にサブ構造が含まれる場合問題の解も最適であり、問​​題は最適な部分構造特性を持っている (つまり、最適化原理を満たしている) と言えます。したがって、部分問題の最適解を通じて問題の最適解を導き出すことができ、また、前段階の状態から後段階の状態を推定できることがわかります。

後遺症なし

つまり、部分的な問題の解決策が決定されると、それはそれ以上変更されず、より大きな問題の解決策の影響を受けません。それを含む問題、意思決定への影響。

後段の状態を導出する場合、前段の状態のみを考慮すればよく、この状態が段階的にどのように導出されるかを気にする必要がないことが簡単に理解できます。 2 つ目の意味は、ある段階のステータスが決定されると、その後の段階の決定には影響されないということです。

部分問題の重複特性

部分問題の重複特性とは、再帰的アルゴリズムを使用して問題を上から下まで解決する場合、毎回生成されるサブ問題は同じではありません。常に新しい問題があり、一部のサブ問題は複数回再計算されます

0-1 ナップザック問題

上記の理論は比較的抽象的で、ナンセンスのようなものですが、古典的なナップザック問題を考えてみましょう。

アイテムが 5 つあり、その重量が 2、2、5、11、4 であるとします。バックパックがあり、それに耐えられる最大重量は 10# です。 # #、バックパックに入れる適切なアイテムを選択してください。組み合わせることができるアイテムの最大重量はいくらですか?

アイテムの組み合わせが異なると、さまざまな状態が得られます。

f を使用できます。 (i, w) は状態を表します。i =index は項目番号を表し、w =weight は現在の総重量を表します。

問題全体は『n』段階で解決する必要があります。各段階では、アイテムをバックパックに入れるかどうかの決定が必要です。決定の結果は 2 つだけです:『入れる』か『入れないでください』。アイテムを決定した後、バックパック内のアイテムの重量にはさまざまな状態が存在するため、各レイヤーの

重複した状態 をマージし、異なる状態のみを残す必要があります。次に、前の層のステータス結果に基づいて、次の層のステータス結果が導出されます。最終的には、すべての項目が決まれば最適な組み合わせが見つかります。

0 番目のアイテム (実際には最初のアイテム。いつものように 0 から添え字を付けます) の重みは 2 で、それをバックパックに入れるかどうかを決定し始めますが、結果は 2 つだけです。バックパックに入れている場合、この時のバックパックの重量は2です。バックパックに入れていない場合、バックパックの重量は0です。

$status[0][として記録します。 0] = true; および $status [0][2] = true; 上記の f(i, w) と同様に、前の桁は項目を表し、後の数字は重量を表します。

最初のアイテムの重さはまだ 2 なので、それについての決定を開始します。意思決定の選択肢は 2 つだけです。バックパックに入れるか、バックパックに入れないか、バックパックのステータスは現在のステータスを決定するために使用されます。最初の項目の決定が完了すると、州は 3 つになります (実際には 4 つの州ですが、1 つ重複している場合はカウントされません。それでも 3 つの異なる州としてカウントされます)。

現在のアイテムをバックパックに入れることが決定され、0 番目のアイテムがバックパックに入れられていない場合、この時点のステータスは $status[1][2 0] = true; =&gt ; $status[1][2 ] = true;
現在のアイテムをバックパックに入れることが決定され、0 番目のアイテムもバックパックに入れられた場合、この時点のステータスは$status[1][2 2] = true; => $status[1][4] = true;

現在のアイテムをバックパックに入れないことが決定された場合で、0番目のアイテムがバックパックに入っていない場合、この時のステータスは$status[1 ][0 0] = true; => $status[1][0] = true; となります。
現在のアイテムをバックパックに入れず、0番目のアイテムをバックパックに入れる決定がなされた場合、この時点のステータスは$status[1][0 2] = true; = > $status[1][2] = true;

where$status[1][2 ] が繰り返され、3 つの結果が生成されます。

以下の項目も同様に推定し、すべての項目が決定するまでステータス配列全体を見つけ、最後の層だけを決定すればよい最大値 (上記の例では 10) に最も近い true の値が、バックパックが保持できる最大値です。次に、端から前に進んで、対応する項目の添え字、つまりどの項目の組み合わせが最適なソリューションの組み合わせであるかを見つけることができます。

導出プロセスは次のとおりです。

実は、上記の導出プロセスは動的プログラミングです。問題解決のアイデア。問題を段階に分割し、各段階が戦略に対応します。次に、各段階の状態を記録し (重複を削除するように注意してください)、現在の状態の可能性から次の段階のすべての可能な状態を推定し、動的に推定します。

PHP 実装疑似コード:

function dynamicKnapsack($arr, $n, $max){
    // 初始化二维数组
    $status = [];
    for ($i = 0; $i = 0; $j--) {
        if ($status[$n - 1][$j] == true) {
            break;
        }
    }
    for ($i = $n - 1; $i >= 1; $i--) { // 外层遍历行
        if ($j - $arr[$i] >= 0 && $status[$i - 1][$j - $arr[$i]] == 1) {
            var_dump('buy this product: '.$arr[$i]);
            $best[] = $i;
            $j = $j - $arr[$i];
        }
    }
    if ($j != 0) {
        var_dump('buy first product:'.$arr[0]);
        $best[] = 0;
    }
    return $best;}// 测试数据$arr = [
    2, 2, 5, 11, 4,];$n = 5;$max = 10;$best = dynamicKnapsack($arr, $n, $max);var_dump($best);

結果が 11 の場合、結果は 4、5、2 の組み合わせになります。質問がありますが、11 という別の結果はありませんか? たまたまそれで十分ですよね?これは実際のニーズに応じて決定すべきだと思います。たとえば、今回の要件は、赤い封筒を有効期限順に並べ替え、期限切れが近づいているものを最初に使用し、データを組み立てるときに、期限切れが近づいている赤い封筒を強制的に配列の最後に配置することです。有効期限順に配列して、最後の 4 有効期限が近づいている赤い封筒です。最初にこの赤い封筒を消費したいのです。4 を使用すると、11 は使用できません。続けることしかできません。正面にあるのを探してください。

概要

このコードの時間計算量はどれくらいですか? 最も時間がかかる部分は、中央のネストされた 2 層ループであり、合計の時間計算量は次のとおりです。 isO(n*max)、ここで、n はアイテムの数を表し、max は最大耐荷重能力を表します。

空間計算量は最初に適用される配列空間ですO(n*max 1)さらに計算結果の累積が発生する可能性がありますO(n*2*max) 状況では、スペース消費量が依然として非常に多くなっています。

一般的に言えば、これは空間を時間と交換するという考え方です。また、中間意思決定の入れ子ループでjを使って小さいものから大きいものまでたどると、forループで計算が繰り返されるという問題が発生します。

推奨される学習: 「PHP ビデオ チュートリアル 」

以上がPHP が動的プログラミングを使用して最適な赤い封筒の組み合わせを実現する方法の詳細な説明の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。