ナップサック問題を動的計画法で解く - 具体例で学ぶ数学
ナップサック問題とは ・荷物が $N$ 個ある ・各 $i$ に対して、$i$ 番目の荷物は重さが $w_i$、価値が $v_i$ ・ナップサックには合計重さ $W$ までしか荷物が入らない ・荷物をナップサックにうまく入れて、価値を最大化したい というのがナップサック問題です。 ※各荷物は「入れるか入れないかの２通り」とします。この問題設定を0-1 ナップサック問題と言います。 ナップサック問題は難しい 単純に考えると、入れる荷物の選び方を全て考えれば解けますが、荷物の選び方は全部で $2^N$ 通りあるので、総当りで解くのは厳しいです。 実際、ナップサック問題はNP困難と呼ばれる（計算量理論において）難しい問題のクラスに属していることが知られています。 動的計画法で解く（方針） $1$ 番目から $i$ 番目までの荷物のみを使って、容量 $w$ のナップサックに詰め込める価値の最大値を
プログラミングコンテストでの動的計画法
2. はじめに • 「動的計画法」は英語で 「Dynamic Programming」 と言います． • 略して「DP」とよく呼ばれます． • スライドでも以後使います． 4. ナップサック問題とは？ • n 個の品物がある • 品物 i は重さ wi, 価値 vi • 重さの合計が U を超えないように選ぶ – 1 つの品物は 1 つまで • この時の価値の合計の最大値は？ 品物 1 品物 2 品物 n 重さ w1 重さ w2 ・・・ 重さ wn 価値 v1 価値 v2 価値 vn 5. ナップサック問題の例 品物 1 品物 2 品物 3 品物 4 U=5 w1 = 2 w2 = 1 w3 = 3 w4 = 2 v1 = 3 v2 = 2 v3 = 4 v4 = 2 品物 1 品物 2 品物 3 品物 4 答え 7 w1 = 2 w2 = 1 w3 = 3 w4 = 2 v1 = 3 v
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
