phpキャッシュボクシングアルゴリズム

PHP はボクシング アルゴリズムを実装します

貪欲な方法は、最適解を追求するのではなく、より満足のいく解決策が得られることだけを望む方法です。貪欲な方法では、最適な解決策を見つけるためにすべての可能性を検討するのに費やさなければならない時間を大幅に節約できるため、通常、満足のいく解決策を迅速に得ることができます。貪欲な方法では、考えられる全体的な状況をすべて考慮せずに、現在の状況に基づいて最適な選択を行うことが多いため、貪欲な方法で後戻りしないでください。
? たとえば、ショッピングで両替する場合、最小の小銭を得るために、さまざまな発行オプションをすべて考慮するのではなく、最も額面の高い通貨から始めて、各通貨を降順に検討します。まず、より大きな額面の通貨を使用するようにしてください。より大きな額面の通貨よりも金額が少ない場合は、次のより小さな額面の通貨を検討してください。これは貪欲な方法を使用しています。このアプローチは、銀行が発行する硬貨の種類と硬貨の額面を巧みに調整しているため、ここでは常に最適です。たとえば、額面がそれぞれ 1、5、11 単位のコインしかなく、合計 15 単位のコインを取得したいとします。貪欲なアルゴリズムによれば、額面 11 単位のコイン 1 枚と額面 1 単位のコイン 4 枚を見つけ、合計 5 枚のコインを回収する必要があります。ただし、最適な解決策は、額面 5 単位のコイン 3 枚である必要があります。
[問題] パッキングの問題
? 問題の説明: パッキングの問題は次のように簡単に説明できます: ボリューム v0、v1 の番号が付けられた n 種類の項目があります。 、…、vn-1。これらの n 個のアイテムを容量 V のいくつかの箱に入れます。これらの n 項目の体積は V を超えないことが合意されています。つまり、0 ≤ i ? n 個の項目の集合を n 個以下の項目に分割するすべてのサブセットを調べると、最適解が見つかります。しかし、可能なすべての分割の合計数が大きすぎます。 n が適度に大きい場合、考えられるすべてのパーティションを見つけるのにかかる時間が法外に長くなります。この目的のために、ビン パッキング問題には非常に単純な近似アルゴリズム、つまり貪欲法が使用されます。このアルゴリズムは、適合する最初のボックスにアイテムを順番に入れます。このアルゴリズムでは、最適な解決策が見つかるとは限りませんが、それでも非常に適切な解決策を見つけることができます。一般性を失わずに、n 個のアイテムのボリュームが大きいものから小さいものへ順序付けされていると仮定します。つまり、v0≧v1≧…≧vn-1 となります。上記の要件が満たされない場合は、n 個の項目をサイズの大きいものから小さいものまで並べ替え、並べ替えの結果に従って項目の番号を付け直します。梱包アルゴリズムは次のように簡単に説明されます。
{ 箱の体積を入力します。
アイテムの数 n を入力します。
各アイテムの体積を大きいものから小さいものへ順に入力します。使用済みボックス チェーンは空です。
使用済みボックス カウンター box_count を 0 に設定します。
for (i=0;i{ 最初の使用済みボックスから開始して、使用可能なアイテムを検索します。アイテム i のボックス j に配置されます。
if (使用済みのボックスにアイテム i を配置できない場合)
{ 別のボックスを使用して、アイテム i をボックスに配置します。
box_count++;
else
Put item i into box j;
}
}
上記のアルゴリズムは、必要なボックスの数、box_count、および各ボックスに含まれるアイテムを見つけることができます。次の例は、このアルゴリズムが必ずしも最適な解決策を見つけるとは限らないことを示しています。その体積が 60、45、35、20、20、および 20 単位である箱の体積は 100 単位です。上記のアルゴリズムに従って計算すると、3 つのボックスが必要で、各ボックス内の項目は次のとおりです。最初のボックスには項目 1 と 3 が含まれ、2 番目のボックスには項目 2、4、および 5 が含まれ、3 番目のボックスには項目 6 が含まれます。最適な解決策は、アイテム 1、4、5 と 2、3、6 をそれぞれ含む 2 つのボックスです。
各ボックスに含まれるアイテムがリンク リストで表される場合、リンク リストのヘッド ノード ポインタは構造体に格納され、その構造体には残りのスペースの量とアイテムのリンク リストの最初のポインタが記録されます。箱に入っています。また、全てのボックスの情報もリンクリスト化される。以下は上記のアルゴリズムに従って書かれたプログラムです。
}

添付の PHP サンプル:

?

<?php
//物品
$items[0] = 60;
$items[1] = 45;
$items[2] = 35;
$items[3] = 20;
$items[4] = 20;
$items[5] = 20;
$box_volume_count = 100; //每个盒 子的最大容积
$box_count = 0; //共用盒子总数
$item_count = count( $items );
$box = array();//盒 子数组
for ( $itemindex = 0; $itemindex < $item_count; $itemindex++ ) {
$_box_index = false;
$_box_count = count( $box );
for ( $box_index = 0; $box_index < $_box_count; $box_index++ ) {
  if ( $box[$box_index]['volume'] + $items[$itemindex] <= $box_volume_count ) {
  $_box_index = $box_index;
  break;
  }
}
if ( $_box_index === false ) {
  $box[$_box_count]['volume'] = $items[$itemindex];
  $box[$_box_count]['items'][] = $itemindex;
  $box_count++;
} else {

  $box[$_box_index]['volume'] += $items[$itemindex];
  $box[$_box_index]['items'][] = $itemindex;
}
}
print_r( $box );
?>

?

出典: http://home.51.com/chenjiuchuan/diary/item/10049598.html