結局分からないナップザック問題(^~^)

でふ(^~^) 公開下書き

結局分からないナップザック問題(^~^)

20210124shogi2a2b1.png
「 じゃあ次。 ナップザック問題って何だぜ?」

kifuwarabe-futsu.png
「 挿入ソートが分かってないのに 先々進むから ますます分からん」

ohkina-hiyoko-futsu.png
「 進んだり 戻ったり すればいいのよ」

ramen-tabero-futsu2.png
「 どんな問題なんだぜ?」

📖 ナップサック問題

ohkina-hiyoko-futsu.png
「 👆 価値と重さの 2つの数を持ったアイテムが いっぱいあって、
決まっている重さに収まるように、最大限の価値を得るように目指すのよ」

ramen-tabero-futsu2.png
「 例題無いの?」

ohkina-hiyoko-futsu.png
「 あっても 著作権上の問題があるわねぇ」

20210701coder4.png

kifuwarabe-futsu.png
「 👆 適当に描いたが、こんなので どうだぜ?」

ramen-tabero-futsu2.png
「 いいんじゃないの」

kifuwarabe-futsu.png
「 で、ナップサック問題って どうやるんだぜ?」

ramen-tabero-futsu2.png
「 分かんね」

📖 D - ナップサック問題

ohkina-hiyoko-futsu.png
「 👆 AtCoder にも置いてあるんだけど、 D問題なのよね」

ramen-tabero-futsu2.png
「 解説読んでみようぜ?」

📖 解説

ramen-tabero-futsu2.png
「 👆 分からん」

kifuwarabe-futsu.png
「 ググってみようぜ?」

📖 Knapsack problem

ohkina-hiyoko-futsu.png
「 👆 海外の方が 分かりやすいこともあるのよ」

20210701coder4a1.png

ramen-tabero-futsu2.png
「 👆 とりあえず 1個 選ぼうぜ」

ramen-tabero-futsu2.png
「 ここからが 分からん」

kifuwarabe-futsu.png
「 ググろうぜ?」

ramen-tabero-futsu2.png
「 NTTデータ数理システムとか 北陸大学とか出てきても 結局基礎があるやつしか読めない記事で わけ分からんから 邪魔なんで検索から除外しよう」

📖 ナップサック問題を動的計画法で解く

ohkina-hiyoko-futsu.png
「 👆 これとか どうなの」

ramen-tabero-futsu2.png
「 まず 総当たりしてみろとのことだぜ」

20210701coder4a2.png

ramen-tabero-futsu2.png
「 👆 確かに 全パターン 見えているなら そこから選ぶだけだぜ」

ohkina-hiyoko-futsu.png
「 でも そんなことしたら 遅いから やっちゃダメなのよ」

ramen-tabero-futsu2.png
「 漸化式(ぜんかしき)って何なんだぜ?」

kifuwarabe-futsu.png
「 1個前の数を使うやつだぜ。フィボナッチ数列みたいなやつ」

ramen-tabero-futsu2.png
「 ナップザック問題で どう使うんだぜ?」

kifuwarabe-futsu.png
「 そこを お父んが ググれだぜ」

20210701coder4a3.png

ramen-tabero-futsu2.png
「 👆 こういう表を作ったらいいのかだぜ?」

ohkina-hiyoko-futsu.png
「 違うんじゃないかなあ。 漸化式 っぽくないもん」

📖 DP(動的計画法)でコイン問題を解くまでの過程メモ

ramen-tabero-futsu2.png
「 👆 分かってるやつは 話しを飛ばすから わけ分からん。
分かってないやつの記事を読もうぜ」

20210702coder5a2.png

ramen-tabero-futsu2.png
「 👆 まず りんご で埋めるのかな」

20210702coder5a3.png

ramen-tabero-futsu2.png
「 👆 次に ぶどう を埋めるんだぜ」

ohkina-hiyoko-futsu.png
「 上の段から りんごをコピーすんの?」

ramen-tabero-futsu2.png
「 コピーしたり、減らしたりするんじゃないか?」

kifuwarabe-futsu.png
「 テーブル引きで 1発じゃないか?」

20210702coder5a4.png

ramen-tabero-futsu2.png
「 👆 ダイナミック・プログラミングな雰囲気が でてきたな」

ohkina-hiyoko-futsu.png
「 weight は どこへ行ったの?」

ramen-tabero-futsu2.png
「 今は 忘れようぜ」

20210702coder5a5.png

ramen-tabero-futsu2.png
「 👆 1つ上の段からコピーすればいいように できてるのかも」

何度でもクリック!→

むずでょ@きふわらべ第29回世界コンピューター将棋選手権一次予選36位

光速のアカウント凍結されちゃったんで……。ゲームプログラムを独習中なんだぜ☆電王戦IIに出た棋士もコンピューターもみんな好きだぜ☆▲(パソコン将棋)WCSC29一次予選36位、SDT5予選42位▲(パソコン囲碁)AI竜星戦予選16位

Crieitは個人で開発中です。 興味がある方は是非記事の投稿をお願いします! どんな軽い内容でも嬉しいです。
なぜCrieitを作ろうと思ったか

また、「こんな記事が読みたいけど見つからない!」という方は是非記事投稿リクエストボードへ!

こじんまりと作業ログやメモ、進捗を書き残しておきたい方はボード機能をご利用ください!

ボードとは?

むずでょ@きふわらべ第29回世界コンピューター将棋選手権一次予選36位 の最近の記事