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

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