首页 | 新闻 | 交流 | 问吧 | 文档 | 手册 | 下载 | 博客

[php]0-1背包回溯

作者:  时间: 2011-06-10

<?php
header("content-type:text/html;charset=utf-8");
/**
*@description
*搜索一颗深度为n(n=物品数量)的树,根节点即第一个物品,如果根接点的重量未超过限定重量,则根左右子节点都是第二个物品,如果超过,则第二个物品只作为左子节点。
*主要思想是,符合限定条件的节点,将搜索左右子树,不符合的的节点,将只搜索左子树
*假设w[] = (2,3,4) p[] = (4,5,6),限重量为7,则最终搜索树为
2
0/ \1
3 3
0/ \1 0/ \1
4 4 4 4
|1 |1 |1 |0
(4) (3,4) (2,4)(2,3) --- 最终可能解,只需判断物品价值最高的一组
*上图中0,1分别代表当前节点是否叠加/或\线上面的节点重量
*假设以上数据,限重变成了4,则最终搜索树为
2
0/ \1
3 3 (因为3 + 2 > 4,所以只搜索左子树)
0/ \1 0/
4 4 4
|1 |0 |0
(4) (3) (2) --- 最终可能解,判断价值最高的一组
*/
class bag01_bt{
public $weight = array();//重量
public $price = array();//价格
public $limitw = 0; //限重
public $n = 0; //树的层级
public $x = array();//底层节点->根节点的叠加节点
public $cx = array();//是否叠加当前节点
public $cp = 0; //叠加节点的总价格
public $cw = 0; //叠加节点的总重量
public $bp = 0; //最优价格
public function bag01_bt($limitw,$weight,$price)
{
$this->n = count($weight);
$this->weight = $weight;
$this->price = $price;
$this->limitw = $limitw;
}

public function backstracking( $n=0 )
{
if($n >= $this->n)
{
if($this->cp > $this->bp )
{
$this->bp = $this->cp;
$this->x = $this->cx;
}
return false;
}
//符合条件,记录当前节点为1,且叠加当前物品重量,继续搜索右子数
if($this->cw + $this->weight[$n] <= $this->limitw)
{
$this->cw += $this->weight[$n];
$this->cp += $this->price[$n];
$this->cx[$n] = 1;
$this->backstracking( $n + 1);
$this->cw -= $this->weight[$n];
$this->cp -= $this->price[$n];
}
//不记录当前节点,不叠加当前物品重量,搜索左子树
$this->cx[$n] = 0;
$this->backstracking( $n + 1);
}
}


$weight = array(2, 3, 44, 5, 15, 12);
$price = array(5, 5, 8, 17, 3, 7);
$limitw = 30;

$bag = new bag01_bt($limitw,$weight,$price);
$bag->backstracking( );
echo "<pre/><br/>";
echo "最优解:";
echo $bag->bp."<br/>";
echo "物品:<br/>";
foreach($bag->x as $k=>$v)
{
if($v == 1) $items[] = $bag->weight[$k]."(".$bag->price[$k].")";
}
print_r($items);
?>