请教各位大神一个变形的背包问题

有N种物品和一个容量为V的背包。还有一个阈值T。
第i种物品最多有n[i]件可用，每件费用是c[i]，价值是w[i]。
求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和大于且最接近T。

附完全背包代码

        /** 
    *背包问题描述：一个承受最大重量为W的背包，现在有n个物品，每个物品重量为t, 每个物品的价值为v。 
    * 要使得这个背包重量最大(但不能超过W),同时又需要背包的价值最大。 
    *思路：定义一个二维数组，一维为物品数量(表示每个物品),二维是重量（不超过最大,这里是10）,下面数组a, 
    *动态规划原理思想，max(opt(i-1,w),wi+opt(i-1,w-wi)) 当中最大值， 
    *opt(i-1,w-wi)指上一个最优解 
    */  
    //这是我根据动态规划原理写的   
    // max(opt(i-1,w),wi+opt(i-1,w-wi))   
    //背包可以装最大的重量   
    $w=10;   
    //这里有四件物品,每件物品的重量   
    $dx=array(3,4,5);   
    //每件物品的价值   
    $qz=array(4,5,6);   
    //定义一个数组   
    $a=array();   
    //初始化   
    for($i=0;$i     for ($j=0;$j     //opt(i-1,w),wi+opt(i-1,w-wi)   
    for ($j=1;$j         for($i=1;$i             $a[$j][$i]=$a[$j-1][$i];   
            //不大于最大的w=10  
            if($dx[$j-1]                 if(!isset($a[$j-1][$i-$dx[$j-1]])) continue;  
                //wi+opt(i-1,wi)  
                $tmp = $a[$j-1][$i-$dx[$j-1]]+$qz[$j-1];   
                //opt(i-1,w),wi+opt(i-1,w-wi) => 进行比较    
                if($tmp>$a[$j][$i]){   
                    $a[$j][$i]=$tmp;   
                }   
            }   
        }   
    }   
    //打印这个数组,输出最右角的值是可以最大价值的   
    for ($j=0;$j         for ($i=0;$i             echo $a[$j][$i]."    ";   
            } echo "
";   
    } 


    ?>  

回复讨论(解决方案)

你遇到了什么问题呢？你的结果应该是对的
不过我喜欢这么写

$w = 10;$ar = array(  array('w' => 3, 'v' => 4),  array('w' => 4, 'v' => 5),  array('w' => 5, 'v' => 6),);foreach($ar as $k=>$v) {  $v['k'][] = $k;  $res[] = $v;}$p = 0;for(;$p<count($res); $p++) {  $r = $res[$p];  foreach($ar as $i=>$v) {    if(in_array($i, $res[$p]['k'])) continue;    if($r['w'] + $v['w'] <= $w) {      $res[] = array(        'w' => $r['w'] + $v['w'],        'v' => $r['v'] + $v['v'],        'k' => array_merge($r['k'], array($i)),      );    }  }}foreach($res as $v) $t[] = $v['v'];array_multisort($t, SORT_DESC, $res); print_r($res);

Array(    [0] => Array        (            [w] => 9            [v] => 11            [k] => Array                (                    [0] => 1                    [1] => 2                )        )    [1] => Array        (            [w] => 9            [v] => 11            [k] => Array                (                    [0] => 2                    [1] => 1                )        )    [2] => Array        (            [w] => 8            [v] => 10            [k] => Array                (                    [0] => 0                    [1] => 2                )        )    [3] => Array        (            [w] => 8            [v] => 10            [k] => Array                (                    [0] => 2                    [1] => 0                )        )    [4] => Array        (            [w] => 7            [v] => 9            [k] => Array                (                    [0] => 0                    [1] => 1                )        )    [5] => Array        (            [w] => 7            [v] => 9            [k] => Array                (                    [0] => 1                    [1] => 0                )        )    [6] => Array        (            [w] => 5            [v] => 6            [k] => Array                (                    [0] => 2                )        )    [7] => Array        (            [w] => 4            [v] => 5            [k] => Array                (                    [0] => 1                )        )    [8] => Array        (            [w] => 3            [v] => 4            [k] => Array                (                    [0] => 0                )        ))

目前这个是 装满了w=10的背包的最大价值。

我是想找出：在尽量装满背包的情况下，总价值接近给定的一个阈值T 的组合

$f = 9;print_r(array_filter($res, function($a) use ($f) { return $a['v'] > 0.9*$f && $a['v']<1.1*$f;}));

太强了，感谢版主大人！非常牛B，结果完全达到了

这个算法你写的太简洁了，有点看不懂，再请教您一下，怎么过滤掉重复的组合啊？ 比如 0 3 6 ，3 0 6，6 0 3

....array_multisort($t, SORT_DESC, $res); //排序（已有的）foreach($res as $i=>$v) if(isset($res[$i-1]) && ! array_diff($res[$i-1]['k'], $v['k'])) unset($res[$i]); //去重$res = array_values($res); //规格化

我这个算法并未完全按照动态规划去做
而是记录了所有可能的组合，最后用排序做检查

太感谢了，多谢您的指教