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

この投稿は xuzuning によって最終編集されました: 2011-06-10 14:40:16

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)、
3. r 配列の各サブセットの項目を対応する v 値に変換し、それぞれ合計します (代入配列 wv)、
4. wv 配列をソートします、取得 より大きな値の鍵は結果です。

2...すべてのサブセット内の項目の合計が w 重みより小さいサブセットを選択します
------------------------ -- ---
は、
{1,3,5} --> (1+3+5) < w
{2,6} --> などのサブセット項目の合計です。 < w

さらに、これはバックトラッキング アルゴリズムとは少し異なります。バックトラッキング アルゴリズムによって計算されるサブセットは順序通りです。ここでの要件によって計算されるサブセットは順序通りではありません。 。 ポイント。

とてもクールなアイデアは良いですね

実際、この質問のアイデアは長い間インターネット上で公開されていました

それは C、C++、さらには C# で書かれていますが、PHP では書かれていません
。
それで見てみたいのですが、私たちの csdn の PHP セクションに、PHP で書いてみたいという熱心な人はいますか

Baidu で PHP で書かれたバックトラッキングのケースが見つかりません

Coolesting には良いアイデアがあります

実際、この質問のアイデアは長い間インターネット上で公開されていました。

C で書かれたものもあれば、C++、さらには C# で書かれたものもありますが、それらは PHP で書かれたものではありません

そこで私は、私たちの csdn の PHP セクションに、PHP で作成する意欲のある熱心な人々がいるかどうかを確認してください

Baidu まで待たないでください。PHP で書かれたバックトラッキング ケースが見つからない

さて、この素晴らしいタスクはあなたに任されています。 ...

アルゴリズムの正しさを検証するために、元のデータと回答を提供することをお勧めします

アルゴリズムは難しいものではなく、最初から他の言語を移植することができます。もちろん、イノベーションの方が良いでしょう

1. w の配列をソートし、w よりも小さい重みを持つ項目を選択します (代入配列 p)、

2. p 配列のデカルト積積配列を計算し、すべてを選択しますサブセット 項目の合計は w の重み (代入配列 r) のサブセットより小さいです。
最初のステップでは 1 次元配列のみが生成されるため、2 番目のステップでデカルト積を計算するにはどうすればよいでしょうか?
組み合わせを探している場合は、非常に簡単です

ボス小言さん、わかりませんでしたか? 1 階では、すべての組み合わせが最初にカウントされ、項目ごとに比較されます

Coolesting より引用。 1階 返信:

1. wの配列をソートし、wより小さい項目(代入配列p)を選択します。
2. p配列のデカルト積配列を計算し、すべての部分集合内の項目を選択しますその合計が w の重みより小さい (代入配列 r) の部分集合、

最初のステップでは 1 次元配列のみが生成されるため、2 番目のステップでデカルト積を計算するにはどうすればよいでしょうか?
組み合わせを探しているのであれば、最初のステップで生成された 1 次元配列の閉包を探しているはずだと言うのは簡単です

全体として、このように考えることができますか。アイテムの必要な重量未満の組み合わせがある場合は、アイテムの値をアイテムの重量で割って比率を取得し、比率を大きいものから小さいものに並べ替え、最小の比率が最大の組み合わせを見つけます。または、前方からの必要重量と同等です。

$ar=array('1'=>'3','4'=>'20','5'=>'3','6'=>'7','2' =>'9','12'=>'8','9'=>'12','10'=>'15','15'=>'6');
$ a=array();
$w=10;//必要な重み
foreach($ar as $key=>$value){
if($key<=$w){$a[$key]= $値;}
}
//print_r($a);
foreach($a as $key=>$value){
$a[$key]=$value/$key
}
arsort($ a );
//print_r($a);
$b=array();
$sum=$sum+$key; if($sum>$w){break;};
$b[$key]=$ar[$key] }

print_r($b);

このように考えていただけますか。アイテムの必要重量に満たない組み合わせのうち、アイテムの価値をアイテムの重量で割って比率を求め、その比率を大きい順に並べ替え、必要な重量以下のものを前から見つけて、比率が最も大きい組み合わせ。

$ar=array('1'=>'3','4'=>'20','5'=>'3','6'=>'7','2' =>'9','12'=>'8','9'=>'12','10'=>'15','15'=>'6');
$ a=array();
$... いいえ、たとえば、9=>8、4=>3、10=>10、3 つのアイテムがあり、バックパックは 11、アルゴリズムは 10=> ;10、そして明らかにそれは 9=>8 であるはずです、4=>3 が正しいです

このように考えていただけますか。アイテムの必要な重量未満のすべての組み合わせで、重量で項目を選択し、比率を取得し、比率を大きい順に並べ替え、必要な重量以下の比率が最も大きい組み合わせを前から探します。

$ar=array('1'=>'3','4'=>'20','5'=>'3','6'=>'7','2' =>'9','12'=>'8','9'=>'12','10'=>'15','15'=>'6');
$ a=array();
$...

このように、同じ価格のアイテムが 2 つ存在することはありませんので、包括的ではありません

必要な重量未満のすべての組み合わせで、このように考えることができますか?アイテムの値をアイテムの重量で割って比率を求め、比率を大きい順に並べて、必要な重量以下の比率が最も大きい組み合わせを前から探します。

$ar=array('1'=>'3','4'=>'20','5'=>'3','6'=>'7','2' =>'9','12'=>'8','9'=>'12','10'=>'15','15'=>'6');
$ a=array();
$w……

重量を表すためにキーを使用し、価格を表すために値を使用します。

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

";?>

10 階の blizzf99 からの返信を引用します:

このように考えることはできますか、必要なアイテムの重量未満のすべての組み合わせにおいて、アイテムの価値をそのアイテムの重量で割ります。比率を取得するアイテムを選択し、この比率を大きい順にソートして計算し、必要な重量以下の比率が最も大きい組み合わせを前から探します。

$ar=array('1'=>'3','4'=>'20','5'=>'3','6'=>'7','2' =>'9','12'=>'8','9'=>'12','10'=>'15','15...

確かに体重は重量が同じ場合は、価格が高い方を選択する必要があります

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

class Backtracking {    private $c = 0;   //背包容量    private $n = 0;   //物品数    private $w = array();   //物品重量数组    private $p = array();   //物品价值数组    private $cw = 0;   //当前重量    private $cp = 0;   //当前价值    private $bestp = 0;   //当前最优价值    private $d;   //单位重量价值  private $st = array();  function __construct($w, $p, $c) {    $this->w = $w;    $this->p = $p;    $this->c = $c;    $this->n = count($w);    $this->d = array_map(array($this, 'Calculation'), $this->p, $this->w);    array_multisort($this->d, SORT_DESC, $this->w, $this->p);  }  private function Calculation($p, $w) {    if($w == 0) return $p;    return $p / $w;  }  function BestValue() {    return $this->bestp;  }  function parse($i=0) {    if($this->debug) echo "-> $i ($this->cw, $this->cp) [".join(',', $this->st)."]<br />\n";    if($i > $this->n - 1) {  //到达叶子节点        $this->bestp = $this->cp;     if($this->debug) echo "<= $i ($this->cw, $this->cp) [".join(',', $this->st)."]<br />\n";      return;      }      $this->st[] = $i;    if($this->cw + $this->w[$i] <= $this->c) {        $this->cw += $this->w[$i];        $this->cp += $this->p[$i];        $this->parse($i + 1); //深度优先       $this->cw -= $this->w[$i];        $this->cp -= $this->p[$i];    }      if($this->Bound($i + 1) > $this->bestp) {  //向前探测        if($this->debug) echo "== $i ($this->cw, $this->cp) [".join(',', $this->st)."]<br />\n";      array_pop($this->st);      $this->parse($i + 1);      }      if($this->debug) echo "<- $i ($this->cw, $this->cp) [".join(',', $this->st)."]<br />\n";  }    private function Bound($i) {      //计算节点所相应价值的上界      $cleft = $this->c - $this->cw;   //剩余容量      $b = $this->cp;      //以物品单位重量价值递减顺序装入物品      while($i < $this->n && $this->w[$i] <= $cleft) {        $cleft -= $this->w[$i];        $b += $this->p[$i];        $i++;      }      if($i <= $this->n) {        $b += $this->d[$i] * $cleft;      }      return $b;    }  function display() {    foreach($this->st as $k)       $r[] = array( 'w' => $this->w[$k], 'v' => $this->p[$k]);     return $r;  }}

# のデータについては、 11
$ar = array(9 =>8, 4=>3, 10=>10);
$p = 新しいバックトラッキング(array_values($ar), array_keys($ar), 11); p->parse();
echo $p->BestValue(); // 13
print_r($p->display());
[0] => w] = ＆gt; 3
配列（1,3）、アレイ（3,2）、配列（9,1）、アレイ（11,7）、アレイ（3,12）、アレイ（ 9,8) , array(7,3));//値 1 は重量を表し、値 2 は価格を表します
$a=array();
$b=array(); array();
for($i=0;$i if($ar[$i][0]<=$w){
$a[$i ] = $ i] [0]; foreach($b as $key=>$value){
$sum =$sum+$a[$key];
if($sum>$w){break;};
$c[]=$ar[ $key];
}
print_r($c);

//开始工作$w = 20;$arrWeight = array(9, 8, 2, 5, 7);$arrValue  = array(12, 10, 7, 11, 3);$arr = array_combine($arrWeight, $arrValue);arsort($arr);$_w = 0;$arrSelect = array();//开始筛选foreach($arr as $key=>$val) {	$_w += $key;	if($_w <= $w) {		$arrSelect[$key] = $val;	}else {		$_w -= $key;  //这里用到了回溯	}}print_r($arrSelect);

妥当かどうかは専門家に聞いてください

$sw = 15;   //背包重量为23$a = array(2, 3, 44, 5, 15, 12); //价值$w = array(5, 5, 8, 10, 3, 7); //重量//键名对应上价值跟重量$count = count($w);$k = 0;$m=0;for ($i = 0; $i < $count; $i++) {	for ($s = 1; $s < $count; $s++) { //$s 为步长		$sumw[$k] = $w[$i];   //总重量		$suma[$k] = $a[$i];   //总价值		$road[$k][] = $i; //保存路径		for ($m = 0; $m < $count; $m++) {			for ($j = $s; $j < $count; $j ++ ) {				if (in_array($j,$road[$k])) {					continue;				}				$sumw[$k] +=$w[$j];				if ($sumw[$k] <= $sw) {					$road[$k][] = $j;					$suma[$k]+=$a[$j];				} else {					break;				}			}		}		$k++;	}}arsort($suma);$max = current($suma);$r = array_keys($suma, $max);echo "MAX:" . $max . "<BR>";//输出路径：重量数组的键名$rr = 1;foreach ($r as $v) {	echo "ROAD" . $rr . ":     " . implode(',', $road[$v]) . "<BR>";	$rr++;}

理解できない場合は、テスト後に実装できると思います。 、質問することができます

MAX:59
ROAD1: 2,4
ROAD2: 4,2

输出结果为

其他的均没有考虑步长的问题，而且重量相同，价值不同的情况也没有过滤

唠叨老大没看出来吗，一楼用的是穷举法，所有的组合先统计出来，然后一项项去比对

可以这么说， 就是穷举法，
因为所有方案中， 可能有m个不同的方案， 但他们的重量和价值比例是相同的，
不把所有子集的项遍历一次， 除非， 只挑一个方案， 就打印结果，

还有， 将质量和价值合并成一个数组的那些答案， 看下面，

//情况一$w = array(2, 8, 2, 5, 7);  //质量$v  = array(12, 10, 7, 11, 3); //价值$arr = array_combine($w, $v);//$arr 结果Array(    [2] => 7    [8] => 10    [5] => 11    [7] => 3)//情况二$w = array(2, 2, 2, 2, 2);$v  = array(12, 14, 7, 11, 3);$arr = array_combine($w, $v);Array(    [2] => 3)

Array
(
[2] => 3
)

#16 楼的答案 $p = new Backtracking(array_values($w), array_values($v), 11);$p->parse();echo $p->BestValue();$p->display();//情况一 $w = array(2, 2, 2, 2, 7);  //质量$v = array(12, 10, 4, 11, 3); //价值//结果40Array(    [0] => Array        (            [w] => 2            [v] => 12        )    [1] => Array        (            [w] => 2            [v] => 11        )    [2] => Array        (            [w] => 2            [v] => 10        )    [3] => Array        (            [w] => 2            [v] => 4        ))//情况二$w = array(2, 8, 3, 2, 7);  //质量$v = array(12, 10, 7, 11, 3); //价值//结果30Array(    [0] => Array        (            [w] => 2            [v] => 12        )    [1] => Array        (            [w] => 2            [v] => 11        )    [2] => Array        (            [w] => 3            [v] => 7        )    [3] => Array        (            [w] => 8            [v] => 10        ))

本帖最后由 xuzuning 于 2011-06-10 13:59:22 编辑

我#16的代码已更新

经多组数据测试，我#16的代码得到的构成有问题
待解决后再参与讨论


$v = array(2, 4, 6, 8, 10);
$w = array(1, 2, 3, 4, 5);

$v = array(1, 2, 3, 4, 5);
$w = array(2, 4, 6, 8, 10);

若要用价值和质量 并成比例去计算的， 要排除这二种情况。

$ar=array('1'=>'3','4'=>'20','5'=>'3','6'=>'7','2'=>'9','12'=>'8','9'=>'12','10'=>'15','15'=>'6');
$a=array();
$w=10;//所需重量
foreach($ar as $key=>$value){
if($key<=$w){$a[$key]=$value;}
}
//print_r($a);
foreach($a as $key=>$value){
$a[$key]=$value/$key;
}
arsort($a);
//print_r($a);
$sum=0;
$b=array();
foreach($a as $key=>$value){
$sum=$sum+$key;
if($sum>$w){break;};
$b[$key]=$ar[$key];
}

print_r($b);

$ar=array('1'=>'3','4'=>'20','5'=>'3','6'=>'7','2'=>'9','12'=>'8','9'=>'12','10'=>'15','15'=>'6');
$a=array();
$w=10;//所需重量
foreach($ar as $key=>$value){
if($key<=$w){$a[$key]=$value;}
}
//pri……


明显不行，而且忘记考虑如果重量一样，价值又一样时候的选择
比如，所需重量是$w=10;
array('2'=>'5','2'=>'5','2'=>'5','2'=>'5','2'=>'5','5'=>'15','5'=>'10','8'=>'15','8'=>'10');

明显('2'=>'5','2'=>'5','2'=>'5','2'=>'5','2'=>'5')与('5'=>'15','5'=>'10')是一样的

把这个放到你的程序里得到



$ar=array('2'=>'5','2'=>'5','2'=>'5','2'=>'5','2'=>'5','5'=>'15','5'=>'10','8'=>'15','8'=>'10');
$a=array();
$w=10;//所需重量
foreach($ar as $key=>$value){
if($key<=$w){$a[$key]=$value;}
}
//print_r($a);
foreach($a as $key=>$value){
$a[$key]=$value/$key;
}
arsort($a);
//print_r($a);
$sum=0;
$b=array();
foreach($a as $key=>$value){
$sum=$sum+$key;
if($sum>$w){break;};
$b[$key]=$ar[$key];
}

print_r($b);
?>

得到结果是 Array ( [2] => 5 [5] => 10 )

PHP code

$sw = 15; //背包重量为23
$a = array(2, 3, 44, 5, 15, 12); //价值
$w = array(5, 5, 8, 10, 3, 7); //重量
//键名对应上价值跟重量
$count = count($w);
$k = 0;
$m=0;
for ($i = 0; $i < $count; $i++) {
……

你的代码也不行

$ar=array(array(1,3),array(3,2),array(4,8),array(9,1),array(11,7),array(3,12),array(9,8),array(7,3));//值1表示重量，值2表示价格
$w=10;
$a=array();
$b=array();
$c=array();
for($i=0;$i if……

<?php$ar=array(array(2,5),array(2,5),array(2,5),array(2,5),array(2,5),array(5,10),array(5,14),array(7,3));//值1表示重量，值2表示价格$w=10;$a=array();$b=array();$c=array();for($i=0;$i<count($ar);$i++){  if($ar[$i][0]<=$w){  $a[$i]=$ar[$i][0];//重量数组  $b[$i]=$ar[$i][1]/$ar[$i][0]; //价格与重量比值数组     }}//print_r($a);//print_r($b);arsort($b);$sum=0;foreach($b as $key=>$value){  $sum=$sum+$a[$key];  if($sum>$w){break;};  $c[]=$ar[$key];}print_r($c);?> 

输出为Array ( [0] => Array ( [0] => 5 [1] => 14 ) [1] => Array ( [0] => 2 [1] => 5 ) [2] => Array ( [0] => 2 [1] => 5 ) )是错误的结果

标准答案应该是Array ( [0] => Array ( [0] => 2 [1] => 5 ) [1] => Array ( [0] => 2 [1] => 5 ) [2] => Array ( [0] => 2 [1] => 5 ) [3] => Array ( [0] => 2 [1] => 5 )[4] => Array ( [0] => 2 [1] => 5 ))

本帖最后由 xuzuning 于 2011-06-10 10:32:06 编辑

为便于测试结果，先发一个枚举的。
当然这与楼主要求并不一致

$bk = 15; //背包$a = array(2, 3, 44, 5, 15, 12); //价值$w = array(5, 5, 8, 10, 3, 7); //重量Knapsack($w, $a, $bk);function Knapsack($w, $a, $bk) {  $k = array_keys($w);  $r = array();  for($i=1; $i<=count($k); $i++) {    $r = array_merge($r, combination($k, $i));  }  foreach($r as $i=>$t) {    $n = 0;    $v = 0;    foreach($t as $p) {      $n += $w[$p];      $v += $a[$p];    }    if($n > $bk) unset($r[$i]);    else {      $mv[$i] = $v;      $mw[$i] = $n;    }  }  array_multisort($mw, SORT_DESC, $mv, SORT_DESC, $r);  foreach($mw as $i=>$v) {    echo "w:$v v:{$mv[$i]} [";    foreach($r[$i] as $k) echo "({$w[$k]},{$a[$k]})";      echo "]\n";  }}

w:15 v:56 [(8,44)(7,12)]
w:15 v:30 [(5,3)(3,15)(7,12)]
w:15 v:29 [(5,2)(3,15)(7,12)]
w:15 v:8 [(5,3)(10,5)]
w:15 v:7 [(5,2)(10,5)]
w:13 v:47 [(5,3)(8,44)]
w:13 v:46 [(5,2)(8,44)]
w:13 v:20 [(10,5)(3,15)]
w:13 v:20 [(5,2)(5,3)(3,15)]
w:12 v:15 [(5,3)(7,12)]
w:12 v:14 [(5,2)(7,12)]
w:11 v:59 [(8,44)(3,15)]
w:10 v:27 [(3,15)(7,12)]
w:10 v:5 [(10,5)]
w:10 v:5 [(5,2)(5,3)]
w:8 v:44 [(8,44)]
w:8 v:18 [(5,3)(3,15)]
w:8 v:17 [(5,2)(3,15)]
w:7 v:12 [(7,12)]
w:5 v:3 [(5,3)]
w:5 v:2 [(5,2)]
w:3 v:15 [(3,15)]