アルゴリズムを思い出してください。アルゴリズムの専門家以外は立ち入るべきではありません

バックトラッキング アルゴリズム。アルゴリズムの専門家以外は立ち入らないでください。

この投稿は、2011-06-10 14:40:16 に xuzuning によって最終編集されました n 個の項目がある場合、それらの重みは w[0]、w[1]、...w[n-1]、項目の値は v[0]、v[1]、...v です。 [それぞれn。-1]、合計重量を保持できるバックパックがありますw。このn個のアイテムから選択したアイテムの合計重量がバックパックの容量wを超えないよう、選択したアイテムの値の合計が最大になるようにアイテム選択計画を設計します。

これは非常に一般的なバックトラッキング アルゴリズムです。PHP で作成できる人はいますか?


注意: アルゴリズムと関係のない返信は容赦なく削除されます。モデレーター

共有先:
-----解決策--------------------------------
この質問には少なくとも 1 時間かかります。私はアイデアについて話しているので、他の人にやってもらいましょう。

1. w の配列をソートし、w より小さい重みを持つ項目を選択します (代入配列 p)、
2. p 配列のデカルト積積配列を計算し、すべてのサブセット内の項目の合計が w 重み (代入配列 r) より小さいサブセットを選択します (代入配列 r)、
3. r 配列の各サブセット内の項目を対応する v 値に変換し、それぞれ合計します (割り当て配列 wv)、
4. wv 配列をソートすると、より大きい値のキーが結果となります。
------解決策-----

<br />
<?php<br />
$m = 15;<br />
$arr = array(array(2,1),array(4,2),array(3,6),array(5,9),array(9,8));//第一个值为价格 ；第二个值为 重量<br />
function Combination($arr, $size = 1) {<br />
    $len = count ( $arr );<br />
    $max = pow ( 2, $len ) - pow ( 2, $len - $size );<br />
    $min = pow ( 2, $size ) - 1;<br />
    $r_arr = array ();<br />
    for($i = $min; $i <= $max; $i ++) {<br />
        $t_arr = array ();<br />
        for($j = 0,$k = 0; $j < $len; $j ++) {<br />
            $a = pow ( 2, $j );<br />
            $t = $i & $a;<br />
            if ($t == $a) {<br />
				$t_arr [] = $arr [$j];<br />
            }<br />
        }<br />
        if (count($t_arr) == $size) {<br />
            $r_arr [] = $t_arr;<br />
        }<br />
    }<br />
    return $r_arr;<br />
}<br />
$num = count($arr);<br />
for($i = 1;$i<=$num;$i++){<br />
	$_tt  =	Combination($arr,$i);<br />
	$num_tt = count($_tt);<br />
	for($j = 0;$j<$num_tt;$j++){<br />
		$_t[] = $_tt[$j];<br />
	}<br />
}//找出所以的可能情况<br />
function check_m($arr,$m,$jk=1) {//$arr 为要判断的数组 $m为重量 $jk为判断的是重量还是价格<br />
	$num_t = count($arr);<br />
	for($i = 0;$i <$num_t ;$i++){<br />
		$num_ti = count($arr[$i]);<br />
		$as = 0;<br />
		for($j=0;$j<$num_ti;$j++){<br />
			$as += $arr[$i][$j][$jk];<br />
		}<br />
		if($as<=$m){<br />
			$_r[] =$arr[$i];<br />
		}<br />
	}<br />
	Return $_r;<br />
}<br />
<br />
<br />
function check_max($arr) {<br />
	$ms = 0;<br />
	$num_t = count($arr);<br />
	for($i = 0;$i <$num_t ;$i++){<br />
		$num_ti = count($arr[$i]);<br />
		$as = 0;<br />
		for($j=0;$j<$num_ti;$j++){<br />
			$as += $arr[$i][$j][0];<br />
		}<br />
		if($as>=$ms){<br />
			$_r = $arr[$i];<br />
		}<br />
		$ms = $as;<br />
	}<br />
	Return $_r;<br />
}<br />
$_rr = check_m($_t,$m,1);<br />
$_r=check_max($_rr);<br />
echo "<pre class="brush:php;toolbar:false">";<br />
print_r($_r);<br />
echo "

";
?>

- - ----解決策------------------

この投稿は、xuzuning によって 2011-06-10 14:01 に最後に投稿されました。 :34 編集

クラスのバックトラッキング { <br>
private $c = 0 //バックパックの容量 <br>
private $n = 0 //アイテム数 <br>
private $w = array() //アイテムの重み配列 <br>
private $p = array() //項目値の配列 <br>
private $cw = 0 //現在の体重 <br>
private $cp = 0; // 現在の値 <br>
private $bestp = 0 //現在の最良値 <br>
private $d; //単位重量値<br>
プライベート $st = array();<br>
<br>
function __construct($w, $p, $c) {<br>
$this->w = $w;<br>
$this->p = $p;<br>
$this->c = $c;<br>
$this->n = count($w);<br>
<br>
$this->d = array_map(array($this, '計算'), $this->p, $this->w);<br>
array_multisort($this->d, SORT_DESC, $this->w, $this->p);<br>
}<br>
<br>
プライベート関数 Calculation($p, $w) {<br>
If($w==0) $p を返します。