→をクリックすると非真理設定が非表示になります。ページを再読み込みすると戻ります。
[約180kg](15 stysien)しか運べない小船の上に、いくつかの品物を載せて運ぶとするとき、最大でどれだけの価値を運べるでしょうか。運ぶ品物の候補は以下の5つです。
一見、1 stysienあたり3000 ledz以上の価値がある品物5を乗せるのが合理的にも見えますが、これを載せてしまうと残り2 stysienしか余裕がないため、あとは品物1しか乗せることができず、最終的に運べる価値は42000 ledzとなります。
一方、品物3と品物4を運べば、ちょうど15 stysienで43000 ledzを運ぶことができます。今回の場合、これが最大です。
ということで、小船の積載制限・品物の質量・品物の価値の情報を元に、運べる最大の価値を求める[指令](cersva)を書いていきましょう。情報は次のように与えられるものとします。
| 自由 | 自由 | 戻る場所 | 小船の積載制限 | 品物の価値の一覧の先頭番地 | 品物の質量の一覧の先頭番地 | 品物の個数 |
なんせ小船ですので、積載制限は200 stysienより小さいものとします。また、単独で積載制限を超える品物も無ければ、質量のない品物も無いものとします。故に品物は多くとも200個です。
さて、今回は、処理を書く前に方針を立てましょう。最初に思いつくのは「それぞれの品物について『選ぶか選ばないか』全ての場合を試し、それぞれについて積載制限を満たしているかどうか確認し、その中で最大を選ぶ」というものかもしれませんが、実はこれだとかなり時間が掛かってしまいます。品物が1個増えるだけで処理時間が倍増してしまうからです。
西暦2018年現在で「10^9 ≒ 2^30ぐらいがループで回して数秒で終わる上限」とか言われているので、現代の高速な環境上で回したとしても品物が50個だと10日規模、55個だと年単位の時間が掛かってしまう。
そこで、次のような方針を立てましょう。
こうすれば、0から200までの201通りのnについての一覧を作る作業を、品物の個数の回数だけ行うだけで十分なので、圧倒的な効率と速度が得られます。
さて、さらに具体化していきましょう。
まず、何も品物を選んでいない状態に関しては簡単です。何も選んでいない以上、価値は当然0なので、価値の最大値も0です。ということで、0で全部埋めたものが一覧表です。
次に、「q個まで見た表」から「q+1個まで見た表」を作る方法を考えていきましょう。
まずは具体例から見ていきましょう。先程の例で、最初の4つまで見たときの表はこうなります。
旧い表： n 価値 0 0 1 2000 2 2000 3 8400 4 10400 5 10400 6 17200 7 19200 8 19200 9 25800 10 27800 11 27800 12 34200 13 36200 14 36200 15 43000
ここに、5つ目の「13 stysienで40000 ledzの価値」の商品を足したときの一覧表を作っていきます。
まず、nが0以上13未満であるときは、5つ目の商品が活躍できるはずがありませんから、新しい表は旧い表の値を複製すればいいだけです。
新しい表： n 価値 0 0 1 2000 2 2000 3 8400 4 10400 5 10400 6 17200 7 19200 8 19200 9 25800 10 27800 11 27800 12 34200 …
一方、nが13以上のときには、5番目の品物を「選ぶか」「選ばないか」という選択肢が生まれます。
具体的には、新しい表のn=13は「旧い表のn=0に新商品の価値40000 ledzを足したもの」と「旧い表のn=13」の比較になります。この場合は、前者の価値が40000 ledzで後者の価値が36200 ledzなので、新商品を選ぶほうが得です。
一方、新しい表のn=15は、「旧い表のn=2に新商品の価値を足したもの」と「旧い表のn=15」の比較になり、今回は前者が42000 ledz、後者が43000 ledzとなるので、新商品を選ばないほうが得です。
さて、ということで方針は立ちました。処理を書いていきましょう。