回溯算法，非算法高手勿进！
本帖最后由 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数组排序， 得出对大的值的键就是结果。
[解决办法]
<?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>";
print_r($_r);
echo "</pre>";
?>
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;
}
}
//开始工作
$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++;
}
//情况一
$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
)
$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";
}
}
class BagPlanning
{
private$containment= 0;//背包容量
private$quantity= 0;//物品数
private$weight= array();//物品重量数组
private$price= array();//物品价值数组
private$result= array();
private$max_result= 0;//最佳结果
private$max_ids= array();//获取最佳结果的物品选择方式
function __construct($containment, $weight, $price)
{
$this->containment= $containment;
$this->weight= $weight;
$this->price= $price;
$this->quantity= count($this->weight);
$this->result= array_fill(0, $this->quantity + 1, array_fill(0, $this->containment + 1, array('best_result' => 0, 'ids' => array())));
$this->bag_planning();
echojoin(',', $this->max_ids), '=', $this->max_result;
}
public function bag_planning()
{
for($i=1;$i<=$this->quantity;++$i)
{
for($j=1;$j<=$this->containment;++$j)
{
if($this->weight[$i-1] <= $j)
{
if($this->price[$i-1] + $this->result[$i-1][$j-$this->weight[$i-1]]['best_result'] > $this->result[$i-1][$j]['best_result'])
{
$this->result[$i][$j]['best_result']= $this->price[$i-1] + $this->result[$i-1][$j-$this->weight[$i-1]]['best_result'];
$this->result[$i][$j]['ids']= array_merge($this->result[$i-1][$j-$this->weight[$i-1]]['ids'], array($i-1));
if($this->result[$i][$j]['best_result'] > $this->max_result)
{
$this->max_result= $this->result[$i][$j]['best_result'];
$this->max_ids= $this->result[$i][$j]['ids'];
}
}
else
{
$this->result[$i][$j]= $this->result[$i-1][$j-$this->weight[$i-1]];
}
}
else
{
$this->result[$i][$j]= $this->result[$i-1][$j];
}
}
}
}
}
$t= new BagPlanning(3, array(1, 2, 3), array(4, 5, 6));
<?php
$weight = array(2, 3, 44, 5, 15, 12);
$price = array(5, 5, 8, 17, 3, 7);
$limitw = 15;
echo "<pre/><br/>";
echo "物品重量<br/>".print_r($weight,1)."<br/>";
echo "对应价格<br/>".print_r($price,1)."<br/>";
echo "限制重量:".$limitw."<br/>========================================<br/>";
echo "不可重复放置同一物品的结果:<br/>";
print_r(bag01_dp($limitw,$weight,$price,false));
echo "可重复放置同一物品的结果:<br/>";
print_r(bag01_dp($limitw,$weight,$price,true));
/**
*@params
*$limitw -- 限重
*$weight -- 重量
*$price -- 价格
*$multiple -- true为可重复放置同一件物品,false表示每件物品只能放一次
*/
function bag01_dp($limitw,$weight,$price,$multiple)
{
$ps = $tp = array();
for($i = 0 ; $i <= $limitw ; $i++) :
foreach( $weight as $k=>$v) :
$o = $i -$v;
$li= $k-1;
$l = $weight[$li];
$lp = !$multiple ? $ps[$o][$l.$li] : max($ps[$o][$l.$li],$ps[$o][$v.$k]);
$lk = ($lp === $ps[$o][$l.$li]) ? $l.$li : $v.$k;
//当前物品重量 <= 当前背包最大承受重量
if( $v <= $i) :
//当前价格 + 剩余价格最优解 > 上次最优解
if( $price[$k] + $lp > $ps[$i][$l.$li]) :
$ps[$i][$v.$k] = $price[$k] + $lp;
$tp[$i][$v.$k] = $tp[$o][$lk];
$tp[$i][$v.$k][] = $v."(".$price[$k].")";
else :
$ps[$i][$v.$k] = $ps[$i][$l.$li];
$tp[$i][$v.$k] = $tp[$i][$lk];
endif;
else :
$ps[$i][$v.$k] = $ps[$i][$l.$li];
$tp[$i][$v.$k] = $tp[$i][$lk];
endif;
endforeach;
endfor;
return array('price'=>end(end($ps)),'items'=>end(end($tp)));
}
?>