本帖最后由 xuzuning 于 2011-06-10 14:40:16 编辑

解决方案 »

  1.   

    这个题至少要一个小时, 我说思路, 让别人做吧。1. 对w的数组排序, 选出小于w重量的项(赋值数组p),
    2. 对p数组计算笛卡尔积乘积阵列,选出所有子集里的项的和小于w重量的子集(赋值数组r),
    3. 对r数组里的每个子集里的项转换成相对应的v值, 并分别求和(赋值数组wv),
    4. 对wv数组排序, 得出对大的值的键就是结果。
      

  2.   

    2 ...... 选出所有子集里的项的和小于w重量的子集
    -----------------------------
    就是对子集项求和, 如
    {1,3,5} --> (1+3+5) < w
    {2,6}   -->  (2+6)  < w
      

  3.   

    coolesting思路不错其实这道题的思路网络上早就有了,有用C写的,也有用C++写的,甚至C#都有,就是没有用PHP写的所以想看看我们csdn的PHP版块是否有热心人愿意用PHP写一个别到时候百度时候找不到PHP写的回溯案例
      

  4.   

    可不可以这样考虑,在所有小于所需物品重量的组合中,用物品的价值除以物品的重量,得到一个比值,对此比值进行由大至小排序,从前面找出小于等于所需重量中最大比值的组合。$ar=array('1'=>'3','4'=>'20','5'=>'3','6'=>'7','2'=>'9','12'=>'8','9'=>'12','10'=>'15','15'=>'6');
    $a=array();
    $w=10;//所需重量
    foreach($ar as $key=>$value){
      if($key<=$w){$a[$key]=$value;}
    }
    //print_r($a);
    foreach($a as $key=>$value){
      $a[$key]=$value/$key;
    }
    arsort($a);
    //print_r($a);
    $sum=0;
    $b=array();
    foreach($a as $key=>$value){
      $sum=$sum+$key;
      if($sum>$w){break;};
      $b[$key]=$ar[$key];
    }print_r($b);
      

  5.   

    不行的,举一个例子,我有9=>8,4=>3,10=>10,三个物品,背包为11,你的算法出来是10=>10,而显然应该是9=>8,4=>3是对的
      

  6.   


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

  7.   

    本帖最后由 xuzuning 于 2011-06-10 14:01:34 编辑
      

  8.   

    $ar=array(array(1,3),array(3,2),array(4,8),array(9,1),array(11,7),array(3,12),array(9,8),array(7,3));//值1表示重量,值2表示价格
    $w=10;
    $a=array();
    $b=array();
    $c=array();
    for($i=0;$i<count($ar);$i++){
      if($ar[$i][0]<=$w){
         $a[$i]=$ar[$i][0];//重量数组
          $b[$i]=$ar[$i][1]/$ar[$i][0]; //价格与重量比值数组  
      }
    }
    //print_r($a);
    //print_r($b);
    arsort($b);
    $sum=0;
    foreach($b as $key=>$value){
      $sum=$sum+$a[$key];
      if($sum>$w){break;};
      $c[]=$ar[$key];
    }
    print_r($c);
      

  9.   

    //开始工作
    $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);麻烦高手看看是否合理
      

  10.   


    $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++;
    }以为我写的代码,测试过是可以的实现的,不理解的,可以提问
      

  11.   

    MAX:59
    ROAD1: 2,4
    ROAD2: 4,2输出结果为
      

  12.   

    还有, 将质量和价值合并成一个数组的那些答案, 看下面, //情况一
    $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
    )Array
    (
        [2] => 3
    )
      

  13.   

    #16 楼的答案 
    $p = new Backtracking(array_values($w), array_values($v), 11);
    $p->parse();
    echo $p->BestValue();
    $p->display();//情况一 
    $w = array(2, 2, 2, 2, 7);  //质量
    $v = array(12, 10, 4, 11, 3); //价值
    //结果
    40Array
    (
        [0] => Array
            (
                [w] => 2
                [v] => 12
            )    [1] => Array
            (
                [w] => 2
                [v] => 11
            )    [2] => Array
            (
                [w] => 2
                [v] => 10
            )    [3] => Array
            (
                [w] => 2
                [v] => 4
            ))
    //情况二
    $w = array(2, 8, 3, 2, 7);  //质量
    $v = array(12, 10, 7, 11, 3); //价值//结果
    30
    Array
    (
        [0] => Array
            (
                [w] => 2
                [v] => 12
            )    [1] => Array
            (
                [w] => 2
                [v] => 11
            )    [2] => Array
            (
                [w] => 3
                [v] => 7
            )    [3] => Array
            (
                [w] => 8
                [v] => 10
            ))
      

  14.   

    本帖最后由 xuzuning 于 2011-06-10 13:59:22 编辑
      

  15.   

    $v = array(2, 4, 6, 8, 10);
    $w = array(1, 2, 3, 4, 5); $v = array(1, 2, 3, 4, 5);  
    $w = array(2, 4, 6, 8, 10);若要用价值和质量  并成比例去计算的, 要排除这二种情况。
      

  16.   

    $ar=array('1'=>'3','4'=>'20','5'=>'3','6'=>'7','2'=>'9','12'=>'8','9'=>'12','10'=>'15','15'=>'6');
    $a=array();
    $w=10;//所需重量
    foreach($ar as $key=>$value){
      if($key<=$w){$a[$key]=$value;}
    }
    //print_r($a);
    foreach($a as $key=>$value){
      $a[$key]=$value/$key;
    }
    arsort($a);
    //print_r($a);
    $sum=0;
    $b=array();
    foreach($a as $key=>$value){
      $sum=$sum+$key;
      if($sum>$w){break;};
      $b[$key]=$ar[$key];
    }print_r($b);
      

  17.   

    明显不行,而且忘记考虑如果重量一样,价值又一样时候的选择
    比如,所需重量是$w=10;
    array('2'=>'5','2'=>'5','2'=>'5','2'=>'5','2'=>'5','5'=>'15','5'=>'10','8'=>'15','8'=>'10');明显('2'=>'5','2'=>'5','2'=>'5','2'=>'5','2'=>'5')与('5'=>'15','5'=>'10')是一样的把这个放到你的程序里得到
    <?php$ar=array('2'=>'5','2'=>'5','2'=>'5','2'=>'5','2'=>'5','5'=>'15','5'=>'10','8'=>'15','8'=>'10');
    $a=array();
    $w=10;//所需重量
    foreach($ar as $key=>$value){
      if($key<=$w){$a[$key]=$value;}
    }
    //print_r($a);
    foreach($a as $key=>$value){
      $a[$key]=$value/$key;
    }
    arsort($a);
    //print_r($a);
    $sum=0;
    $b=array();
    foreach($a as $key=>$value){
      $sum=$sum+$key;
      if($sum>$w){break;};
      $b[$key]=$ar[$key];
    }print_r($b);
    ?> 得到结果是 Array ( [2] => 5 [5] => 10 ) 
      

  18.   


    <?php$ar=array(array(2,5),array(2,5),array(2,5),array(2,5),array(2,5),array(5,10),array(5,14),array(7,3));//值1表示重量,值2表示价格
    $w=10;
    $a=array();
    $b=array();
    $c=array();
    for($i=0;$i<count($ar);$i++){
      if($ar[$i][0]<=$w){
      $a[$i]=$ar[$i][0];//重量数组
      $b[$i]=$ar[$i][1]/$ar[$i][0]; //价格与重量比值数组   
      }
    }
    //print_r($a);
    //print_r($b);
    arsort($b);
    $sum=0;
    foreach($b as $key=>$value){
      $sum=$sum+$a[$key];
      if($sum>$w){break;};
      $c[]=$ar[$key];
    }
    print_r($c);
    ?> 
    输出为Array ( [0] => Array ( [0] => 5 [1] => 14 ) [1] => Array ( [0] => 2 [1] => 5 ) [2] => Array ( [0] => 2 [1] => 5 ) )是错误的结果标准答案应该是Array ( [0] => Array ( [0] => 2 [1] => 5 ) [1] => Array ( [0] => 2 [1] => 5 ) [2] => Array ( [0] => 2 [1] => 5 ) [3] => Array ( [0] => 2 [1] => 5 )[4] => Array ( [0] => 2 [1] => 5 ))
      

  19.   

    本帖最后由 xuzuning 于 2011-06-10 10:32:06 编辑
      

  20.   

    function combination($ar, $k, $m=0, $a=array()) {
            static $ret = array();
            if($m == 0) {
                    $m = count($ar);
                    $ret = array();
            }
            for($i=$m; $i>=$k; $i--) {
                    $a[$k-1] = $ar[$i-1];
                    if($k > 1) {
                            combination(&$ar, $k-1, $i-1, $a);
                    }else {
                            array_unshift ($ret, array_reverse($a));
                    }
            }
            return $ret;
    }
      

  21.   

    呵呵……的确是0/1背包问题趁中午,贴个动态规划算法。写得比较匆忙
    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();

    echo join(',', $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));
    0,1=9
      

  22.   

    http://www.cppblog.com/ivenher/articles/1776.html
    這是一篇cpp的回溯算法,你可以借鉴一下他的编程思想来用php完成.
      

  23.   

    好热闹,踩一脚。
    之前写过动态规划的,根据上面同学的测试样例,在同重不同价的数据源下发现有bug,趁这个帖子,改过下.
    回溯/贪心法等有空再复习整理下。
     <?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)));
    }
    ?>
      

  24.   

    http://topic.csdn.net/u/20110609/16/ff2287c0-5cad-48f0-a388-e5d1c7c20f19.html?seed=1109966163&r=73786713#r_73786713
    他这个有点类似,
      

  25.   

    原来估计大家都知道,这道题其实可以用
    1.贪婪法  
    2.回溯法 
    3.动态规划 
    4.递归 
    都可以解的出来不过原理归原理,真的写起来你会发现要考虑的问题蛮多的,特别没有人用PHP写过看看这里这么多人写的,有几人可以用的
      

  26.   

    总算整理出来了
    <?php
    /**
    *@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);
    ?>
      

  27.   

    #73$weight     = array(3,7,4,6,10,12);
    $price      = array(3,7,6,4,10,32); 
    $limitw     = 10;The height weight :10
    Products:
    Array
    (
        [0] => 3(3)
        [1] => 7(7)
    )
      

  28.   

    $ar=array('1'=>'3','4'=>'20','5'=>'3','6'=>'7','2'=>'9','12'=>'8','9'=>'12','10'=>'15','15'=>'6');
    $a=array();
    $w=10;//所需重量
    foreach($ar as $key=>$value){
      if($key<=$w){$a[$key]=$value;}
    }
    //print_r($a);
    foreach($a as $key=>$value){
      $a[$key]=$value/$key;
    }
    arsort($a);
    //print_r($a);
    $sum=0;
    $b=array();
    foreach($a as $key=>$value){
      $sum=$sum+$key;
      if($sum>$w){break;};
      $b[$key]=$ar[$key];
    }print_r($b);
      

  29.   

    这能对吗,都不是所有路径搜索。你怎么知道asort排完序后,一定要叠加上最开头的值?
    你试下上面测试用的数据源。$ar=array('3'=>'3'
             ,'7'=>'7'
             ,'4'=>'6'
             ,'6'=>'4'
             ,'10'=>'10'
             ,'12'=>'32'
             ,'5'=>'5');
    $a=array();
    $w=10;//所需重量
      

  30.   

    public function getArray()
      {
      $arr1 = array (
      '0' => array ('fid' => 1, 'tid' => 1, 'name' => 'Name1' ),
      '1' => array ('fid' => 1, 'tid' => 2 , 'name' => 'Name2' ),
      '2' => array ('fid' => 1, 'tid' => 5 , 'name' => 'Name3' ),
      '3' => array ('fid' => 1, 'tid' => 7 , 'name' => 'Name4' ),
      '4' => array ('fid' => 3, 'tid' => 9, 'name' => 'Name5' )
      );
      $arr2 = array();
      foreach ($arr1 as $key => $value)
      {
      $arr2[$valuewww.overlookworld.com= array('tid' => $value['tid'],'name' => $value['name']);
      }
      return $arr2;
      

  31.   

    这个不是回溯问题吧,这个是动态规划问题,是一个很经典的背包问题。
    baidu一下背包问题就会有了,挺简单的。记得之前去暴风影音面试C++的时候笔试题的程序题中就有一题是背包问题要当时写出可运行程序。
      

  32.   


    function PackAri($maxweig, $weigs, $valus){
    //$maxweig--最大承重
    //$weigs--重量数组
    //$valus--价值数组
      //首先排除单个重量大于$maxweig的
      foreach($weigs as $key => $value){
        if($value > $maxweig){
         unset($weigs[$key]);
         unset($valus[$key]);
        }
      }  //进行重量数组元素的排列组合
      $weig_tmp = array();
      $valu_tmp = array();
      $weig_ret = array();
      $valu_ret = array();
      do{
        $weig_tmp[] = array_pop($weigs);
        $valu_tmp[] = array_pop($valus);
    foreach($weig_tmp as $key => $value){ //左结合
      $weig_ret[] = array_merge($weigs, array($value));
      $valu_ret[] = array_merge($valus, array($valu_tmp[$key]));
    }
    foreach($weigs as $key => $value){ //右结合
      $weig_ret[] = array_merge($weig_tmp, array($value));
      $valu_ret[] = array_merge($valu_tmp, array($valus[$key]));
    }
      }while(count($weigs) > 1);  //再次排除总重量大于规定的
      foreach($weig_ret as $key => $value){
        if(array_sum($value) > $maxweig){
          unset($weig_ret[$key]);
          unset($valu_ret[$key]);
        }
      }  //选出最大价值的元素
      $maxkey = key($valu_ret);
      $maxval = array_sum(current($valu_ret));
      while($value = current($valu_ret)){
    $sum = array_sum($value);
    if($sum > $maxval){
      $maxval = $sum;
      $maxkey = key($valu_ret);
    }
    next($valu_ret);
      }  //返回结果
      if(isset($weig_ret)){
       $result["weig"] = $weig_ret[$maxkey];
       $result["valu"] = $valu_ret[$maxkey];
       return $result;
      }else return false;
    }$m1 = 110;
    $w1 = array(23, 34, 45, 56, 49, 230, 12, 446);
    $v1 = array(25, 11, 34, 23, 65, 56, 23, 45);
    $test1 = PackAri($m1, $w1, $v1);
    var_dump($test1);$m2 = 30;
    $w2 = array(2, 3, 44, 5, 15, 12);
    $v2 = array(5, 5, 8, 17, 3, 7);
    $test2 = PackAri($m2, $w2, $v2);
    var_dump($test2);
      

  33.   

    想了一个比较笨的方法。
    总重量是W。
    首先各物品按重量从小到大排序,w[0],w[1],...,w[i],...w[n]
    其次,把物品重量大于W的去掉,即w[i]<=W,保留物品[0],w[1],...,w[i]
    然后物品重量拆分W:
      假定W=5,w[0]=1,w[1]=2,w[0]=3,w[3]=4
      取法:
      保留4,压入3,判断(4+3)>5,舍去3,压入2,判断(4+2)>5,舍去2,压入1,判断(4+1)!>5,保留1。取得第一组值4,1
      保留3,压入2,判断(3+2)!>5,保留2,压入1,判断(3+2+1)>5,舍去1,取得第二组数据3,2
      保留3,压入1,判断(3+1)!>5。取得第三组数据3,1
      保留2,压入1,判断(2+1)!>5。取得第三组数据2,1拆分完毕之后再根据价值计算最大价值和
      

  34.   

     final int w_count=10;
            int v_count=0;
            int w[]=new int[]{4,5,1,3,2};
            int v[]=new int[]{8,3,9,7,10};
            Arrays.sort(w);
            Arrays.sort(v);
            int weight=0; 
            for(int i=0 ;i<w.length;i++){
                if ((weight + w[i]) > w_count){
                    break ; 
                }
                weight+=i;
                v_count+=v[i];
            }
    System.out.print("最大值为: "+v_count);
    楼主 这种算法还是蛮简单的