結局分からないナップザック問題（＾～＾）

「　じゃあ次。　ナップザック問題って何だぜ？」

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

「　進んだり　戻ったり　すればいいのよ」

「　どんな問題なんだぜ？」

📖　ナップサック問題

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

「　例題無いの？」

「　あっても　著作権上の問題があるわねぇ」

「　👆　適当に描いたが、こんなので　どうだぜ？」

「　いいんじゃないの」

「　で、ナップサック問題って　どうやるんだぜ？」

「　分かんね」

📖　D - ナップサック問題

「　👆　AtCoder にも置いてあるんだけど、 D問題なのよね」

「　解説読んでみようぜ？」

📖　解説

「　👆　分からん」

「　ググってみようぜ？」

📖　Knapsack problem

「　👆　海外の方が　分かりやすいこともあるのよ」

「　👆　とりあえず　１個　選ぼうぜ」

「　ここからが　分からん」

「　ググろうぜ？」

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

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

「　👆　これとか　どうなの」

「　まず　総当たりしてみろとのことだぜ」

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

「　でも　そんなことしたら　遅いから　やっちゃダメなのよ」

「　漸化式（ぜんかしき）って何なんだぜ？」

「　１個前の数を使うやつだぜ。フィボナッチ数列みたいなやつ」

「　ナップザック問題で　どう使うんだぜ？」

「　そこを　お父んが　ググれだぜ」

「　👆　こういう表を作ったらいいのかだぜ？」

「　違うんじゃないかなあ。　漸化式　っぽくないもん」

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

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

「　👆　まず　りんご　で埋めるのかな」

「　👆　次に　ぶどう　を埋めるんだぜ」

「　上の段から　りんごをコピーすんの？」

「　コピーしたり、減らしたりするんじゃないか？」

「　テーブル引きで　１発じゃないか？」

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

「　weight　は　どこへ行ったの？」

「　今は　忘れようぜ」

「　👆　１つ上の段からコピーすればいいように　できてるのかも」