ナップサック問題はNP困難と呼ばれる難しい問題のクラスに属していることが知られていますが、
ここでは、単純に考えて、入れる商品の選び方を全て考えて解きます。
ただし商品ｎの選び方は全部で 2のｎ乗通り通りあるので、商品の数ｎに制限をつけて計算します。
ナップサック問題は、「価値と容量さが決まっている複数の品物を容量が一定のナップサックに詰め込むとき、 ナップサックに詰め込める品物の価値の和の最大値にするにはどの品物を選べばよいか」という問題です。 ナップサックの容量とそれぞれの品物の容量、価値を入力すれば、簡単に求められます。
|
ナップサック問題はNP困難と呼ばれる難しい問題のクラスに属していることが知られていますが、
|