第i种物品最多有n[i]件可用，每件费用是c[i]，价值是w[i]。
求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和大于且最接近t。
附完全背包代码
进行比较
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$v) { if(in_array($i, $res[$p]['k'])) continue; if($r['w'] + $v['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']$v) if(isset($res[$i-1]) && ! array_diff($res[$i-1]['k'], $v['k'])) unset($res[$i]); //去重$res = array_values($res); //规格化
我这个算法并未完全按照动态规划去做
而是记录了所有可能的组合，最后用排序做检查
太感谢了，多谢您的指教