回溯算法，非算法高手勿进！
本帖最后由 xuzuning 于 2011-06-10 1￥本文来%源[email protected]搞@^&代*@码)网5搞gaodaima代码4: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数组排序， 得出对大的值的键就是结果。
——解决方案——————–
<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="prettyprint linenums">";<br />print_r($_r);<br />echo "
“;
?>
——解决方案——————–
本帖最后由 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;
搞代码网（gaodaima.com）提供的所有资源部分来自互联网，如果有侵犯您的版权或其他权益，请说明详细缘由并提供版权或权益证明然后发送到邮箱[email protected]，我们会在看到邮件的第一时间内为您处理，或直接联系QQ：872152909。本网站采用BY-NC-SA协议进行授权
转载请注明原文链接：回想算法，非算法高手勿进 
