CodeIQ過去問集05：大きなナップサック
本稿はCodeIQで2013年12月16日～2014年1月20日に出題された「大きなナップサック」という問題を再編集したものです。 ※出題時と記述が一部異なる場合がありますがご了承ください。
大きなナップサック
【問題】
容量の決まったナップサックに、できるだけ価値が大きくなるようにものを詰め込む問題を、ナップサック問題といいます。特に、詰め込む品物1つ1つについて、「入れる」・「入れない」の2通りずつしか案のないものを、01ナップサックと言ったりします。
01ナップサックは、品物の数をn個とすると、すべての場合が2のn乗通りあり、品物が多くなると非常に大きな計算量になってしまいます。大規模なナップサック問題を解くためには、探索時にうまく枝刈りをしたり、動的計画法(DP)を利用しなければなりません。
今回は、かなり大きな01ナップサック問題を用意しましたので、うまく工夫をしてできるだけ良い解を見つけてください。
【データのフォーマットと具体例】
入力ファイル(*.in.txt)のフォーマットは、次のようになっています。
N B v1 w1 v2 w2 . . . vN wN
Nは品物の数、Bはナップサックの容量です。 wの合計が、B以下で、その場合のvの合計値が最大になるような選び方を求め、出力は1行目にvの合計、2行目には、N個のしなものについて、選ぶ場合は1、選ばない場合は0を出力してください。
以下はサンプルのデータです。まず、サンプルで正しく計算できることを確認してから、本番のデータにチャレンジしてみましょう。
sample.in.txt
10 382 109 73 114 86 97 72 108 77 115 89 92 60 100 70 90 64 119 95 103 78
sample.out.txt
530 1100111000
サンプルデータの説明
1100111000という値は、1,2,5,6,7番目の品物を選ぶという意味で、この場合、価値は
109 + 114 + 115 + 92 + 100 = 530
で、容量の合計は
73 + 86 + 89 + 60 + 70 = 378
と、制約条件である382以下になっています。
【解答方法】
まずは大きなナップサック.zipをダウンロードしてください。zipファイルを展開すると、いくつかのテキストファイルが入っています。
sample.in.txt
sample.out.txt
具体例で示したデータが書かれています。プログラムのチェック用に活用してください。
- problem.in.txt
ここに書かれているデータを入力値としてください。
- extra
追加データが入っています。
