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
![プログラミングコンテストでの動的計画法](https://cdn-ak-scissors.b.st-hatena.com/image/square/5ef057cc39ae1a12840a6b5051147dd05abcfe00/height=288;version=1;width=512/https%3A%2F%2Fcdn.slidesharecdn.com%2Fss_thumbnails%2Fdynamicprogramming-100328100739-phpapp02-thumbnail.jpg%3Fwidth%3D640%26height%3D640%26fit%3Dbounds)