アルゴリズムとデータ構造 補足資料10-3 「ナップザック問題」 横浜国立大学 理工学部 数物・電子情報系学科 富井尚志 バックトラックアルゴリズム • とりあえずやってみる • ダメなら戻って別の道を探る – あのとき別の道を選んでいたら、、、 • 試行錯誤（trial and error） – 結局全部のケースをやってみる（完全解） – その中で最適な解を選ぶ （最適解を覚えておく） ナップザック問題（Knapsack problem） A) n個の品物を旅行カバンの中に入れて旅行す る．持って歩ける重量には制限がある B) 個々の品物には，重さ と 価値（重要度） の情 報が与えられている． C) n個の品物からいくつか選択して，制限重量 以下で価値の総和が最大になるようにする． ナップザック問題（Knapsack problem） 重量制限が500gのとき 現在の最大総価値0点 本 傘 下着 ジャケット 薬 MDプレーヤ 地図 宿チケット 航空券 洗面用具 10点 90点 90点 30点 100点 20点 70点 100点 100点 50点 500g 500g 300g 1,000g 20g 400g 200g 10g 10g 300g ナップザック問題（Knapsack problem） 重量制限が500gのとき 現在の最大総価値10点 傘 下着 ジャケット 薬 MDプレーヤ 地図 宿チケット 航空券 洗面用具 90点 90点 30点 100点 20点 70点 100点 100点 50点 500g 300g 1,000g 20g 400g 200g 10g 10g 300g 本 10点 500g 500g； あと一つ載せたらOUT ナップザック問題（Knapsack problem） 重量制限が500gのとき 現在の最大総価値90点 本 下着 ジャケット 薬 MDプレーヤ 地図 宿チケット 航空券 洗面用具 10点 90点 30点 100点 20点 70点 100点 100点 50点 500g 300g 1,000g 20g 400g 200g 10g 10g 300g 傘 90点 500g 500g； あと一つ載せたらOUT ナップザック問題（Knapsack problem） 重量制限が500gのとき 現在の最大総価値90点 本 傘 薬 MDプレーヤ 地図 宿チケット 航空券 洗面用具 10点 90点 100点 20点 70点 100点 100点 50点 500g 500g 20g 400g 200g 10g 10g 300g 下着 90点 300g ジャケット 30点 1,000g 1,300g； OUT ナップザック問題（Knapsack problem） 重量制限が500gのとき 現在の最大総価値190点 本 傘 MDプレーヤ 地図 宿チケット 航空券 洗面用具 10点 90点 20点 70点 100点 100点 50点 500g 500g 400g 200g 10g 10g 300g 下着 90点 300g ジャケット 薬 30点 100点 1,000g 20g 1,300g； OUT 320g； ナップザック問題（Knapsack problem） 重量制限が500gのとき 現在の最大総価値190点 本 傘 地図 宿チケット 航空券 洗面用具 10点 90点 70点 100点 100点 50点 500g 500g 200g 10g 10g 300g 下着 90点 300g 薬 100点 ジャケット 20g 30点 1,000g 1,300g； OUT MDプレーヤ 20点 400g 720g；OUT 320g； ナップザック問題（Knapsack problem） 重量制限が500gのとき 現在の最大総価値190点 本 傘 宿チケット 航空券 洗面用具 10点 90点 100点 100点 50点 500g 500g 10g 10g 300g 下着 90点 300g 薬 320g； 100点 ジャケット 20g 30点 1,000g 1,300g； OUT MDプレーヤ 地図 20点 70点 400g 200g 720g；OUT 520g；OUT ナップザック問題（Knapsack problem） 重量制限が500gのとき 現在の最大総価値290点 本 傘 航空券 洗面用具 10点 90点 100点 50点 500g 500g 10g 300g 下着 90点 300g ジャケット 薬 320g； 100点 宿チケット 20g 100点 30点 1,000g 1,300g； OUT MDプレーヤ 地図 20点 70点 400g 200g 720g；OUT 520g；OUT 10g 330g； ナップザック問題（Knapsack problem） 重量制限が500gのとき 現在の最大総価値390点 本 傘 洗面用具 10点 90点 50点 500g 500g 300g 下着 90点 300g ジャケット 薬 320g； 100点 宿チケット 20g 100点 30点 1,000g 1,300g； OUT MDプレーヤ 地図 20点 70点 400g 200g 720g；OUT 520g；OUT 10g 330g； 航空券 100点 10g 340g； ナップザック問題（Knapsack problem） 重量制限が500gのとき 本 傘 10点 90点 500g 500g 現在の最大総価値390点 下着 90点 300g ジャケット 薬 320g； 100点 宿チケット 20g 100点 30点 1,000g 1,300g； OUT MDプレーヤ 地図 20点 70点 400g 200g 720g；OUT 520g；OUT 10g 330g； 航空券 340g； 100点 10g 洗面用具 50点 640g；OUT 300g ナップザック問題（Knapsack problem） 重量制限が500gのとき 本 傘 10点 90点 500g 500g 現在の最大総価値390点 下着 90点 300g ジャケット 薬 320g； 100点 宿チケット 20g 100点 30点 1,000g 1,300g； OUT MDプレーヤ 地図 20点 70点 400g 200g 720g；OUT 解候補 現在の最大総価値390点 520g；OUT 10g 330g； 航空券 340g； 100点 10g 洗面用具 50点 640g；OUT 300g ナップザック問題（Knapsack problem） 重量制限が500gのとき 現在の最大総価値390点 本 傘 薬 MDプレーヤ 地図 宿チケット 航空券 洗面用具 10点 90点 100点 20点 70点 100点 100点 50点 500g 500g 20g 400g 200g 10g 10g 300g 下着 90点 ジャケット 30点 1,000g 1,300g； OUT 300g ナップザック問題（Knapsack problem） 1 1 1 1 1 1 1 1 1 1 本 傘 下着 ジャケット 薬 MDプレーヤ 地図 宿チケット 航空券 洗面用具 10点 90点 90点 30点 100点 20点 70点 100点 100点 50点 500g 500g 300g 1,000g 20g 400g 200g 10g 10g 300g ～ 0 0 0 0 0 0 0 0 0 0 本 傘 下着 ジャケット 薬 MDプレーヤ 地図 宿チケット 航空券 洗面用具 10点 90点 90点 30点 100点 20点 70点 100点 100点 50点 500g 500g 300g 1,000g 20g 400g 200g 10g 10g 300g 最悪時： 上記の全とおりの組み合わせについて、総重量と総価値を計算して、 一番良いものを選ぶ。 O(2n) バックトラックアルゴリズム • とりあえずやってみる • ダメなら戻って別の道を探る – あのとき別の道を選んでいたら、、、 • 試行錯誤（trial and error） – 結局全部のケースをやってみる（完全解） – その中で最適な解を選ぶ （最適解を覚えておく）
© Copyright 2024 ExpyDoc
