回想算法，非算法高手勿进

回溯算法，非算法高手勿进！
本帖最后由 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数组排序， 得出对大的值的键就是结果。
------解决方案--------------------

$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 "
";

print_r($_r);

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;