言わずと知れたナップサック問題は、動的計画法を用いると最適解を商品の個数とナップサックの容量に対して1次のオーダーで計算することができます。 また、この問題については近似解法が知られています. とりあえず2通りの近似解法を知っているので, 動的計…