回溯算法，非算法高手勿进！

本帖最后由 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. 对w的数组排序, 选出小于w重量的项(赋值数组p),
2. 对p数组计算笛卡尔积乘积阵列，选出所有子集里的项的和小于w重量的子集(赋值数组r)，
3. 对r数组里的每个子集里的项转换成相对应的v值， 并分别求和（赋值数组wv),
4. 对wv数组排序， 得出对大的值的键就是结果。

2 ...... 选出所有子集里的项的和小于w重量的子集
-----------------------------
就是对子集项求和， 如
{1,3,5} --> (1+3+5)  {2,6}   -->  (2+6)  

另外， 这个和回溯算法有点不同， 回溯算法计算出来的子集是有顺序的， 
这里的需求计算出来的子集是没顺序的 ， 更像是计算笛卡尔乘积多点。

coolesting思路不错

其实这道题的思路网络上早就有了，

有用C写的，也有用C++写的,甚至C#都有，就是没有用PHP写的

所以想看看我们csdn的PHP版块是否有热心人愿意用PHP写一个

别到时候百度时候找不到PHP写的回溯案例

coolesting思路不错

其实这道题的思路网络上早就有了，

有用C写的，也有用C++写的,甚至C#都有，就是没有用PHP写的

所以想看看我们csdn的PHP版块是否有热心人愿意用PHP写一个

别到时候百度时候找不到PHP写的回溯案例

好,这个伟大的任务就交给你了......

为验证算法的正确性，建议给出原始数据和答案

算法不难，从其他语言移植过来就可以。当然有创新就更好了

1. 对w的数组排序, 选出小于w重量的项(赋值数组p),
2. 对p数组计算笛卡尔积乘积阵列，选出所有子集里的项的和小于w重量的子集(赋值数组r)，
第一步只产生了一维数组，那么第二步的笛卡尔积如何计算呢？
如果是求组合，那倒还简单

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

引用 1 楼 coolesting 的回复:
1. 对w的数组排序, 选出小于w重量的项(赋值数组p),
2. 对p数组计算笛卡尔积乘积阵列，选出所有子集里的项的和小于w重量的子集(赋值数组r)，

第一步只产生了一维数组，那么第二步的笛卡尔积如何计算呢？
如果是求组合，那倒还简单 他说错了吧，应该是求第一步产生的一维数组的闭包吧

可不可以这样考虑，在所有小于所需物品重量的组合中，用物品的价值除以物品的重量，得到一个比值，对此比值进行由大至小排序，从前面找出小于等于所需重量中最大比值的组合。

$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 }
//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();
$…… 不行的，举一个例子，我有9=>8，4=>3，10=>10，三个物品，背包为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();
$……

像这样 就不能出现 两个价格相同的物品啦；所以说不去全面

可不可以这样考虑，在所有小于所需物品重量的组合中，用物品的价值除以物品的重量，得到一个比值，对此比值进行由大至小排序，从前面找出小于等于所需重量中最大比值的组合。

$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 = new Backtracking(array_values($ar), array_keys($ar), 11);
$p->parse();
echo $p->BestValue(); // 13
print_r($p->display());

Array
(
    [0] => Array
        (
            [w] => 3
            [v] => 4
        )

    [1] => Array
        (
            [w] => 8
            [v] => 9
        )

)

$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($ar[$i][0]      $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);

//开始工作$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 }
//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 }
//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 }
//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     ……

你的代码也不行

$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)]