→をクリックすると非真理設定が非表示になります。ページを再読み込みすると戻ります。
予め断っておきますが、今回はかなり長くなります。
まず、与えられた情報を加工したり、作業用の領域を確保することから始めましょう。
最初に与えられた情報はこうですが、
| 自由 | 自由 | 戻る場所 | 積載制限 | 価値一覧 | 質量一覧 | 品物の個数 |
| f5@ | f5+4@ | f5+8@ | f5+12@ | f5+16@ |
f5より小さい番地に、前回言及した作業用の一覧表（0から積載制限まであれば十分なので、長さは積載制限+1）を2つ確保し、さらに[メモ](firjal)の不足を補うために作業領域をさらに3つ確保します。
最終的に、[住所箱](setistafar)を次のように使っていくことを目標とします。また、一覧表1を0で埋める作業もこの段階でやっておきましょう。
| 一覧表2 | … | 一覧表2 | 一覧表1 | … | 一覧表1 | 領域3 | 領域2 | 領域1 | 戻る場所 | 積載制限 | 価値一覧 | 質量一覧 | 品物の個数 |
| f5@ | f5+4@ | f5+8@ | f5+12@ | f5+16@ | f5+20@ | f5+24@ | f5+28@ |
まず、積載制限+1をf0に入れ、それの4倍をf3に入れます。
nll plelajnefes kRz f5+4@ f0 ata 1 f0 kRz f0 f3 dRo 2 f3 …
次に、3つの作業領域を確保するためにf5を12減らし、領域3には一覧表2の先頭番地を入れ、領域2には一覧表1の先頭番地を入れます。
nll plelajnefes kRz f5+4@ f0 ata 1 f0 kRz f0 f3 dRo 2 f3 nta 12 f5 kRz f5 f5+4@ nta f3 f5+4@ kRz f5+4@ f5@ nta f3 f5@ …
以後「f5+12@」などと言った場合は、12引いた方の新しいf5で言及したいので、12引く場所をずらしておきます。
nll plelajnefes nta 12 f5 kRz f5+16@ f0 ata 1 f0 kRz f0 f3 dRo 2 f3 kRz f5 f5+4@ nta f3 f5+4@ kRz f5+4@ f5@ nta f3 f5@ …
そうしたら、一覧表1を先頭から0で埋めていきます。「積載制限+1」が既にf0に入っているので、これを減らしていけばちょうど一覧表1の全体が0で埋まります。
nll plelajnefes nta 12 f5 kRz f5+16@ f0 ata 1 f0 kRz f0 f3 dRo 2 f3 kRz f5 f5+4@ nta f3 f5+4@ kRz f5+4@ f5@ nta f3 f5@ nta f3 f5 nll iumes kRz 0 f5@ ata 4 f5 nta 1 f0 fi f0 0 niv malkRz iumes xx
さて、下ごしらえが終わったので、主となる処理を書いていきましょう。
基本的構造は次のようになります。
[内の](ostor)では「q個まで見た表」から「q+1個まで見た表」を作っていきます。nを増やしながら表を埋めていくという方針を前回立てましたが、ostorが始まる直前にf0に0を入れ、マスを埋めながらf0を4ずつ増やしていきます。
[外](tykuv)では、見る品物の個数を1個ずつ増やしていくという方針に合わせて、領域1であるf5+8@に0を入れ、4ずつ増やしていきます。さらに、領域3と領域2に入っている値を入れ替えることで、「新しい表」と「旧い表」の立場を交換し、次の処理に進みます。
ここでともに4ずつ増やしていっているのは、後で要素にアクセスするのを楽にするためです。
… kRz 0 f5+8@ nll tykuv kRz 0 f0 nll ostor fi … f0 xylo malkRz tykuvon_stodup xx … ata 4 f0 kRz ostor xx nll tykuvon_stodup fi f5+8@ … clo malkRz lesback xx inj f5@ f5+4@ f5@ ata 4 f5+8@ kRz tykuv xx nll lesback …
指令の頭で積載制限であるf5+16@を4倍しておくことで、ostorを終了してtykuvon_stodupに飛ぶための条件としてf5+16@との比較を用いることができるようになります。
nll plelajnefes nta 12 f5 kRz f5+16@ f0 ata 1 f0 kRz f0 f3 dRo 2 f3 dRo 2 f5+16@ kRz f5 f5+4@ nta f3 f5+4@ kRz f5+4@ f5@ nta f3 f5@ nta f3 f5 nll iumes kRz 0 f5@ ata 4 f5 nta 1 f0 fi f0 0 niv malkRz iumes xx kRz 0 f5+8@ nll tykuv kRz 0 f0 nll ostor fi f5+16@ f0 xylo malkRz tykuvon_stodup xx … ata 4 f0 kRz ostor xx nll tykuvon_stodup fi f5+8@ … clo malkRz lesback xx inj f5@ f5+4@ f5@ ata 4 f5+8@ kRz tykuv xx nll lesback …
lesbackに向かうための条件は、領域1であるf5+8@が、品物の数-1の4倍に等しくなることです。これまた比較が楽になるよう、予めf5+28@から1を引いて4倍しておきます。
nll plelajnefes nta 12 f5 nta 1 f5+28@ dRo 2 f5+28@ kRz f5+16@ f0 ata 1 f0 kRz f0 f3 dRo 2 f3 … … … … nll tykuvon_stodup fi f5+8@ f5+28@ clo malkRz lesback xx
さて、基本的な骨組みもできたことですし、あとは細かい部分を埋めていくだけです。
まずは最後の部分から。f5@には新しい表の先頭番地が入っているので、それと積載制限の4倍であるf5+16@との和の番地を見ることで、新しい表の積載制限番目を見ることができます。それが答えなので、f0に入れ、f5を元の位置に戻してkRz f5@ xxします。
nll lesback kRz f5@ f0 ata f5+16@ f0 kRz f0@ f0 ata 12 f5 kRz f5@ xx
さあ、あとは表を埋める処理を書けば完成です。
を順当に2003lkに落とし込んで行きましょう。
f0がnの4倍なので、まずは旧い表の番地（f5+4@）にf0を足し、@することで旧い表のnでの値が入ります。
nll ostor fi f5+16@ f0 xylo malkRz tykuvon_stodup xx kRz f0 f2 ata f5+4@ f2 kRz f2@ f2 … ata 4 f0 kRz ostor xx
その後は、f5+8@に入っている「何番目の品物を見ているか」という情報（ただし1引いて4倍した値が入っている）を質量一覧の先頭番地f5+24@に足し、@することで品物の質量が手に入ります。それをf3に入れておきます。
nll ostor fi f5+16@ f0 xylo malkRz tykuvon_stodup xx kRz f0 f2 ata f5+4@ f2 kRz f2@ f2 kRz f5+8@ f3 ata f5+24@ f3 kRz f3@ f3 … ata 4 f0 kRz ostor xx
nが十分小さいときは、それ以上の判断は要らず、新しい表の番地（f5@）にf0を足して@してf2（旧い表のnでの値）を複製すればよいです。
nll ostor fi f5+16@ f0 xylo malkRz tykuvon_stodup xx kRz f0 f2 ata f5+4@ f2 kRz f2@ f2 kRz f5+8@ f3 ata f5+24@ f3 kRz f3@ f3 kRz f3 f1 dRo 2 f1 fi f1 f0 llo malkRz lasyk xx … nll lasyk kRz f0 f3 ata f5@ f3 kRz f2 f3@ ata 4 f0 kRz ostor xx
さて、あとは比較が必要な場合を処理するだけです。少しややこしいので、具体例に立ち戻って考えてみましょう。
新商品が13 styで40000 ledzのとき、新しい表のn=13は「旧い表のn=0に新商品の価値40000 ledzを足したもの」と「旧い表のn=13」の比較になり、新しい表のn=15は、「旧い表のn=2に新商品の価値を足したもの」と「旧い表のn=15」の比較になるのでした。
とりあえず、旧い表のn=「f0の4分の1であるnから品物の質量f3を引いた値」を見にいきましょう。表を見に行く際に足す番地はどうせ4倍されるので、f0からf3の4倍を引いた値を手に入れ、
nll ostor fi f5+16@ f0 xylo malkRz tykuvon_stodup xx kRz f0 f2 ata f5+4@ f2 kRz f2@ f2 kRz f5+8@ f3 ata f5+24@ f3 kRz f3@ f3 kRz f3 f1 dRo 2 f1 fi f1 f0 llo malkRz lasyk xx kRz f0 f1 dRo 2 f3 nta f3 f1 … nll lasyk kRz f0 f3 ata f5@ f3 kRz f2 f3@ ata 4 f0 kRz ostor xx
旧い表の番地（f5+4@）とそれを足して@した値をf3に入れておきます。
nll ostor fi f5+16@ f0 xylo malkRz tykuvon_stodup xx kRz f0 f2 ata f5+4@ f2 kRz f2@ f2 kRz f5+8@ f3 ata f5+24@ f3 kRz f3@ f3 kRz f3 f1 dRo 2 f1 fi f1 f0 llo malkRz lasyk xx kRz f0 f1 dRo 2 f3 nta f3 f1 kRz f1 f3 ata f5+4@ f3 kRz f3@ f3 … nll lasyk kRz f0 f3 ata f5@ f3 kRz f2 f3@ ata 4 f0 kRz ostor xx
f5+8@に入っている「何番目の品物を見ているか」という情報（ただし1引いて4倍した値が入っている）をf5+20@に入っている価値一覧の先頭番地に足し合わせ、@することで品物の価値をf3に足し合わせます。これで片方の候補の値が手に入ります。
nll ostor fi f5+16@ f0 xylo malkRz tykuvon_stodup xx kRz f0 f2 ata f5+4@ f2 kRz f2@ f2 kRz f5+8@ f3 ata f5+24@ f3 kRz f3@ f3 kRz f3 f1 dRo 2 f1 fi f1 f0 llo malkRz lasyk xx kRz f0 f1 dRo 2 f3 nta f3 f1 kRz f1 f3 ata f5+4@ f3 kRz f3@ f3 kRz f5+8@ f1 ata f5+20@ f1 ata f1@ f3 … nll lasyk kRz f0 f3 ata f5@ f3 kRz f2 f3@ ata 4 f0 kRz ostor xx
あとは、f0とf5@の和の@（新しい表のn番目）にf3（新商品を採用したときの最大価値）を入れ、かなり前にセットしたf2（旧い表のnでの値）と比較、f2の方が大きかったら新しい表のn番目にはf2を入れます。そしてlasykの後の代入処理は飛ばします。
nll ostor fi f5+16@ f0 xylo malkRz tykuvon_stodup xx kRz f0 f2 ata f5+4@ f2 kRz f2@ f2 kRz f5+8@ f3 ata f5+24@ f3 kRz f3@ f3 kRz f3 f1 dRo 2 f1 fi f1 f0 llo malkRz lasyk xx kRz f0 f1 dRo 2 f3 nta f3 f1 kRz f1 f3 ata f5+4@ f3 kRz f3@ f3 kRz f5+8@ f1 ata f5+20@ f1 ata f1@ f3 kRz f0 f1 ata f5@ f1 kRz f3 f1@ fi f1@ f2 xylo malkRz f2 f1@ kRz ostoron_stodup xx nll lasyk kRz f0 f3 ata f5@ f3 kRz f2 f3@ nll ostoron_stodup ata 4 f0 kRz ostor xx
これで完成です。
最終的にこうなります。
nll plelajnefes nta 12 f5 nta 1 f5+28@ dRo 2 f5+28@ kRz f5+16@ f0 ata 1 f0 kRz f0 f3 dRo 2 f3 dRo 2 f5+16@ kRz f5 f5+4@ nta f3 f5+4@ kRz f5+4@ f5@ nta f3 f5@ nta f3 f5 nll iumes kRz 0 f5@ ata 4 f5 nta 1 f0 fi f0 0 niv malkRz iumes xx kRz 0 f5+8@ nll tykuv kRz 0 f0 nll ostor fi f5+16@ f0 xylo malkRz tykuvon_stodup xx kRz f0 f2 ata f5+4@ f2 kRz f2@ f2 kRz f5+8@ f3 ata f5+24@ f3 kRz f3@ f3 kRz f3 f1 dRo 2 f1 fi f1 f0 llo malkRz lasyk xx kRz f0 f1 dRo 2 f3 nta f3 f1 kRz f1 f3 ata f5+4@ f3 kRz f3@ f3 kRz f5+8@ f1 ata f5+20@ f1 ata f1@ f3 kRz f0 f1 ata f5@ f1 kRz f3 f1@ fi f1@ f2 xylo malkRz f2 f1@ kRz ostoron_stodup xx nll lasyk kRz f0 f3 ata f5@ f3 kRz f2 f3@ nll ostoron_stodup ata 4 f0 kRz ostor xx nll tykuvon_stodup fi f5+8@ f5+28@ clo malkRz lesback xx inj f5@ f5+4@ f5@ ata 4 f5+8@ kRz tykuv xx nll lesback kRz f5@ f0 ata f5+16@ f0 kRz f0@ f0 ata 12 f5 kRz f5@ xx