Home >Backend Development >PHP Tutorial >回溯算法，非算法高手勿进！
回溯算法，非算法高手勿进！
- WBOYOriginal
- 2016-06-23 14:27:05890browse
给定物品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……
确实是没考虑到重量相同的情况，如果重量相同，应该取价格高的那个。
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
$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 ))
我#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
<?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 ))
为便于测试结果，先发一个枚举的。
当然这与楼主要求并不一致
$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)]