なっとく!アルゴリズムを読んで  実際の思考経過

セル[i][j] = 1,前の最大値(セル[ i - 1] [ j ] の値)

      2, 現在の品物の価値 + 残りのスペースの価値

                 ↑セル[i - 1] [ j - 品物の重さ]

この式を、このグリッドの全てのセルで使うことができます。あなたのグリッドもこのグリッドと同じになるはずです。部分問題の解き方の説明を覚えれいるでしょうか。2つの部分問題の解を組み合わせることで、より大きな問題を解いたのです。

 

ナップザック問題のあれこれ

まだ魔法のような気がしているかもしれませんね。ここでは、よくある質問に応えることとします。

 

1,品物を追加するとどうなるか

以前は気づかなかった、4つ目の品物を盗めることに気づいたとします。iphoneも盗むことができます。

この新しい品物を考慮に入れるとしたら、最初から何もかも計算し直さなければならないのでしょうか。そんなことはありません。動的計画法が推定値に基づいて問題を徐々に解いていくことを思い出してください。これまでの最大値があります。

4ポンドのナップザックでは、3500ドル分の品物を盗むことができます。それが最終的な最大値であると考えましたが、ここでiphoneの行を追加してみましょう。

 

あたらしい最大値が判明します。続きを読む前に、この新しい行を埋めてみてください。最初のセルから始めましょう。このiphoneは1ポンドのナップザックに入ります。これまでの最大値は1500ドルでありましたが、iphoneには2000ドルの価値があります。代わりにiphone(I) を盗むことにしましょう。

→次のセルには、iphoneとギターが収まります。

 

3つ目のセルでも、iphoneとギターを盗む方が良いので、そのままにします。

最後のセルで、面白いことが起きます。現在の価値は3500ドルです。代わりにiphoneを盗むとすると、3ポンド分の空きが生じます。

  3500(ノートPC+ギター)VS (2000 iphone + ??? 

3ポンド分の空き)

 

それらの3ポンドには、2000ドル分の価値があります。iphoneの2000ドルと古い部分問題による2000 ドルを足すと、4000ドルになります。これが新しい最大値です。 新しい最終グリッドは次のようになります。

 

ここで質問です、 列の値がそもそも「減少」することはあるのでしょうか。そのようなことはあり得るのでしょうか。

 

答えは、いいえです。次のセルに進むたびに現在の最大推定値を書き込んでいくのですから、最大推定値が以前よりも小さくなることはありません。

 

 

勉強のやり始めについて

集中のスイッチの入れ方について、結構大変だなあと、一人で考えている。

一つに決めていても、それを何回かやって行くうちに慣れていって効果がなくなってしまう。ああ今日はもう無理かな、と思った頃に、ようやく頭の片隅が動き始める。多分、このパターンを明日覚えていたとしても、明日は同じようにはいかないのだと思う。 むずかしい。でも、焦らず、腐らず、こつこつと、反省しつつ、落ち込まず、細切れでも。

眠い

眠い時、今この眠さに従うべきか、抗うべきかを考える。

体の声に従いすぎると、楽に流れていってしまう。といって、体の声を無視しすぎると、無意識に集中力や、体の調子が落ちていってしまう。

 

むずかしい。

CODE FESTIVAL 2017 qual A をやってみた

おはようございます。

が、まるで歯が立たなかった.......無念。

とりあえず、アルゴリズムについても、まずはその通りにやればいい問題が解けて、しかるのちにちょっと数学的に考える問題を考えられるようになるのかなあ、とも感じた。

焦らず、腐らず、ひとつ、ひとつ。

大学の授業を聞くということ

今日、授業を受けていて、感じたことを少し。

 

今日、受けた授業の先生は、非常にお話のうまい方だった。というのは、年金と社会保障についてのものだったのだが、主張したい内容を、世の中の常識的な考え方と対立させて、話されていたからだ。

 

その場、集中して聞いていても、わかる話とわからない話がある。今日の授業を集中して聞けた理由は2つくらいあると思っていて、一つは内容が基本的なものであったということ、もう一つは、話の途中で「わかった気にさせる」例えや、あえてする極端な批判が、話が右から左へ流れるのを、防いでいたからだと感じた。

 

この二つの要素だが、話し手からみて、これを考えるのは大変なわりに、話し手の満足度は変わらないように思う。自分の主張、思考過程をそのまま話しても、あるいはそこに、「わかった気にさせる」例えを使って、相手を引きつけても、そこで話されることの本質は変わらないからだ。逆に、そのまま話す、ということを諦めるようでいて、普段から学問に真摯に向き合っていればこそ、面倒なことでありがちなものではないのかと感じる。

 

しかし、私が今日集中して話を聞けたのは、明らかにその本質から外れた部分によって、であった。そういうはなし。

 

将棋の対局について

私は以前、人と将棋を指す時に、定石オタクなのに序盤が弱い、と言われた。

 

つまり、将棋の序盤戦において必要な力は二つあると思っていて、研究によって勝負のスタート地点を有利にしておく意味と、自分の研究範囲外の局面が出てきた時に、バランスをとって戦う力である。この二つは、同時に伸ばすことは結構大変ではないかと、少なくとも当時のぼくは感じていた。

 

将棋も、2段を超えてくると、本に載っているような変化は、大体相手は(気合の入っていない早指しネット対局などを除いて)さして来なくなる。

(近年は、高段者向けの本も出されているので必ずしもその限りではないがしかし、とりあえず有段者くらいの人が高段者向けの本を読み解き、腹落ちさせ、実戦での使用に耐えうるレベルで理解暗記することには、それ単体で多大な労力と甲斐性を要することであるので、それが難なくできる方には、これから話すような、鍛える能力の分類、なんて話は当たらない。ただ、強くなるために、あらゆる努力をすれば良いということだ。)

将棋の中飛車戦法について

将棋を始めて本格的にやろうと思ったとき、本屋に行く前に、自陣3段目までの駒を、「ぼくのかんがえたさいきょうのじんけい」に、組んでみたことがあった。

 

今思うと、それは、寸分たがわず、角交換型の先手中飛車の、片美濃囲い78金、59飛車型だった。本屋に行って、「鈴木大介の将棋 中飛車編」に、まったく同じ陣形が出ていたのをみて、びっくりしたことを覚えている。