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

有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<=10;$i++){ $a[0][$i]=0; }
for ($j=0;$j<=3;$j++){ $a[$j][0]=0; }
//opt(i-1,w),wi+opt(i-1,w-wi)
for ($j=1;$j<=3;$j++){
for($i=1;$i<=10;$i++){
$a[$j][$i]=$a[$j-1][$i];
//不大于最大的w=10
if($dx[$j-1]<=$w){
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<=3;$j++){
for ($i=0;$i<=10;$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$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); //规格化

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

太感谢了，多谢您的指教