変形リュックについて質問させていただきます。

N種類のアイテムとVの容量のバックパックがあります。閾値 T もあります。
利用可能な i 番目のアイテムは最大で n[i] 個あり、各アイテムのコストは c[i]、値は w[i] です。
これらのアイテムのコストの合計がバックパックの容量を超えず、値の合計が T より大きく、T に最も近くなるように、どのアイテムをバックパックに詰めることができるかを調べます。

バックパックの完全なコードを添付します

(i-1,w-wi))
//バックパックは最大重量に耐えることができます
$w=10;
// ここには 4 つのアイテムがあり、各アイテムの重量
$dx=array(3,4,5 );
//各項目の値
$qz=array(4,5,6);
=0;$ i for ($j=0;$j //opt(i-1) ,w),wi+opt(i-1,w-wi)
for ($j=1;$j for($i =1;$iwi+opt（i-1、wi）i-1、w）、wi+opt（i-1、w-wi）=＆gt ; 比較$i]=$tmp;
for ($j=0;$j for ($i=0;$i echo $a [$j][$i]."    "
}echo "< ;br> ";

ディスカッションへの返信 (解決策)

どのような問題が発生しましたか?結果は正しいはずです
でも、私はこのように書くのが好きです

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

が強すぎます、モデレーターありがとう！とても素晴らしいです。結果は完全に達成されています

あなたが書いたこのアルゴリズムは簡潔すぎて少し理解できないのですが、繰り返しの組み合わせを除外するにはどうすればよいですか?たとえば、 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); //规格化

私のアルゴリズムは完全に動的計画法に基づいているわけではありません
代わりに、考えられるすべての組み合わせを記録し、最後に並べ替えを使用してチェックします

本当にありがとう、ありがとうとてもアドバイス