遺伝的アルゴリズムによるナップサックDPのやり方（これもDP）

遺伝的アルゴリズムによるナップサックDPのやり方（これもDP）

1. （これがナップサックDP独特の部分）g当たりの平均値を求め近似解$A$を出す。
   2.袋の数$n=1$兆とかの場合もあるが、まず近似解を利用して平均値のより高い2, 3, 4, 5個の組$X$を作る。これは射になる。
   そこから更に、それを2, 3, 4, 5個組み合わせた射を作る。
   これを繰り返し、$100$個程度の元を持つ空間$Y$を作る。途中からMC法で作る。
   3.近似解から、$Y$の元同士で交換し総当たりでより良い値$B$がないか探す。必ず$A\leqq B$。MC法で$B$を更新し、最終的には総当り。一つずつ射を逆に辿り、最後に$X$。MC法から総当り。