ホームページ  >  記事  >  バックエンド開発  >  バックトラッキング アルゴリズム、アルゴリズムの専門家以外は立ち入らないでください。

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

WBOY
WBOYオリジナル
2016-06-23 14:27:05871ブラウズ

この投稿は 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) 3e1ce6abef3440ef2c16c1b3fdfc1e3d などのサブセット項目の合計です。 b4d3967311b29399b0dc4abef5a75b29$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] $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($key335f64511ffcb02387b0811428104cda$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($keyce9385c0f5dd9a3dd906170b5dc5b664'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')是一样的

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


624bb3231fe135f4df92f81ccd7409e8'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($key335f64511ffcb02387b0811428104cda$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 6f2c9811c89ee5fec56eeeb2cdb7bb0e 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)]

声明:
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。