. Momousagi Academy)
Momousagi Academy)
Momousagi Academy)

うさぎでもわかるアルゴリズム 動的計画法

ナップサック問題（ナップサックもんだい、Knapsack problem）は、計算複雑性理論における計算の難しさの議論の対象となる問題の一つで、「容量 \( C \) のナップサックが一つと、\( n \) 種類の品物（各々、価値 \( p_i \), 容積 \( c_i \)）が与えられたとき、ナップサックの容量 \( C \) を超えない範囲でいくつかの品物をナップサックに詰め、ナップサックに入れた品物の価値の和を最大化するにはどの品物を選べばよいか」という整数計画問題である。

[引用元：ナップサック問題-wikipedia]

(2) ナップサック問題にチャレンジ！

問題 寿司屋の食べ放題

  • 縦が数字の個数 \( n \)
  • 横が0から限界カロリー \( l \) までの限界カロリー
  • 表に埋めるのはカロリーの最大値ではなく、金額の最大値（求めたいのはそれぞれの限界kcal以内で食べれる寿司の最大金額なため）
  • 5つの寿司ともカロリーが10kcal単位なので、表に埋めるのも10kcal単位にする（計算ステップ数が1/10になるので10倍早く結果が出せる）
(3) ナップサック問題のソースコード C言語 #include #define N 5 // 寿司の種類 #define KCAL_MAX 30 // 限界カロリー [×10] int sushi_choice(int cost_list[N],int kcal_list[N]) < int tmp_choice, tmp_not_choice; int table[N][KCAL_MAX+1]; // DP表の一番上（i = 0）を初期化 for(int j = 0; j j) < table[0][j] = 0; // 1品目を食べられない >else < table[0][j] = cost_list[0]; // 1品目を食べられる >> for(int i = 1; i < N; i += 1) < for(int j = 0; j j) < table[i][j] = tmp_not_choice; // カロリーオーバー >else < tmp_choice = table[i-1][j - kcal_list[i]] + cost_list[i]; if(tmp_choice >= table[i-1][j]) table[i][j] = tmp_choice; else table[i][j] = tmp_not_choice; > > > return table[N-1][KCAL_MAX]; > int main() < int cost_list[N] = ; // それぞれのネタの値段 int kcal_list[N] = ; // それぞれの値段のカロリー [×10] int max_cost = sushi_choice(cost_list,kcal_list); printf("%2dkcal以内で食べられる金額の最大：%3d円\n",KCAL_MAX * 10,max_cost); return 0; > Python def sushi_choice(cost_list,kcal_list,limit): list_len = len(kcal_list) dp_table = [[0 for j in range(limit + 1)] for i in range(list_len)] # 1品目を食べるか食べないか for j in range(limit + 1): if kcal_list[0] j: # カロリーオーバー dp_table[i][j] = tmp_not_choice # 食べられない else: tmp_choice = dp_table[i-1][j - kcal_list[i]] + cost_list[i] dp_table[i][j] = max(tmp_choice,tmp_not_choice) return dp_table[list_len - 1][limit] cost = [120,150,140,110,100] # それぞれの寿司の値段 kcal = [8,10,7,6,7] # それぞれの寿司のカロリー [×10] ans = sushi_choice(cost,kcal,30) print(ans) (4) 動的計画法によるナップサック問題の計算量
  • 縦が商品の個数分（\( n \) 個）
  • 横が0からカロリー \( l \) までの \( l+1 \) 個

そのため、処理ステップ数は部分和問題と同じく\[n(l+1) = nl + n\]となり、\( nl + n \) ステップ数と求められます。

よって、計算量をオーダーで表すと \( O(nl) \) となります。

（空間計算量も、表を記憶する分だけかかると考えてもらえたらOKです！ 今回の場合は \( O(nl) \) となります。）

５．さいごに

  • 一定金額以内なら食べ放題のとき、どんなメニューで頼めばちょうどの金額で食べられるか
  • ある商品の中から何品か選んだときにちょうど1,000円となるような組み合わせは何通りあるか

*1 : 導出の際には差分方程式を解きます。実際に、\[a_ = a_ + a_, \ \ a_ = 0, \ \ a_ = 1\]の漸化式（差分方程式）を解くと、\[a_n = \frac < \sqrt> \left( \left( \frac < 2 >\right)^ - \left( \frac < 2 >\right)^ \right)\]となるので、大きい項である\[\frac < \sqrt> \left( \frac < 2 >\right)^\]を取ることでオーダーが求められます。もし差分方程式の解き方に興味がある人はこちらの記事を御覧ください。

公開日： 2020年5月25日 更新日： 2022年11月15日 この記事を書いた人 コメント一覧 コメントはありません。 関連記事 うさぎでもわかる線形代数 第11羽 線形写像（前編） 線形写像の判定・表現行列 【∀, ∃がある式の読み方】うさぎでもわかる離散数学 第3羽 述語論理のいろは うさぎでもわかる計算機システム（基本情報対応） Part19 仮想記憶とページング（4GBの壁の正体は？） 【2021共通テスト】確率分布と統計的な推測 うさぎでもわかる解説 基本情報対策 うさぎでもわかるセキュリティ 前編 うさぎでもわかる信号処理・制御工学 第11羽 フーリエ変換 【基本情報対策】うさぎでもわかるソフトウェア工学 Part08 UML後編（シーケンス図・ユースケース図・アクティビティ図） うさぎでもわかるオートマトンと言語理論 第06羽 Myhill-Nerodeの定理・正則でない言語の証明法 うさぎでもわかる線形代数 補充3 平面の方程式 うさぎでもわかるε-δ論法・ε-N論法

カテゴリー

各種便利ツール・問い合わせ
  • 【完全無料】離散数学演習ツール・計算機まとめ
    • 【ハッセ図】上界/下界・最大元/最小元・極大元/極小元・上限(最小上界)/下限(最大下界) 判定ツール
    • 【ハッセ図】述語論理（∀・∃）真偽判定ツール
    • 【離散数学】べき集合 2^A・P(A) 自動計算＆全列挙ツール
    • 【離散数学】真理値表 自動作成ツール（途中式あり）
    • 【離散数学】集合の「∈・⊆」真偽チェッカー（答え合わせ用）
    • 【離散数学テスト対策】真理値表の穴埋めガチ演習ツール
    • 【離散数学テスト対策】集合の「∈・⊆」ガチ演習！ 弱点分析つき○×ドリル
    【真理値表マスター】うさぎでもわかる離散数学 第2羽 ブール代数と論理演算 うさぎでもわかる離散数学 第5羽 順序関係とハッセ図・重要な8つの性質 【新入生必見】ここだけは押さえよう！ 大学生活完全ガイド 10日で完成！ うさぎでもわかる統計的な推測 8日目 イカサマを見抜け！ 仮説検定のいろは うさぎでもわかる確率・統計 重回帰分析 【統計学】出口調査の仕組みを理解するためのいろは

    目次

    1. １．動的計画法とは
      1. 動的計画法のイメージ
      1. (1) 動的計画法を使わない場合（再帰法）
        1. ソースコード（再帰法）
        1. ソースコード（メモ化再帰）
        1. ソースコード（動的計画法によるフィボナッチ数列の計算）
        1. (1) とりあえず全探索
          1. ソースコード（全探索）
          1. 処理の流れ
          1. C言語
          2. Python
          1. (1) ナップサック問題とは
          2. (2) ナップサック問題にチャレンジ！
          3. (3) ナップサック問題のソースコード
            1. C言語
            2. Python

             工業大学生ももやまのうさぎ塾 (Momousagi Academy)

            コンピュータグラフィックス コンピュータビジョン
            1. １．動的計画法とは
              1. 動的計画法のイメージ
              1. (1) 動的計画法を使わない場合（再帰法）
                1. ソースコード（再帰法）
                1. ソースコード（メモ化再帰）
                1. ソースコード（動的計画法によるフィボナッチ数列の計算）
                1. (1) とりあえず全探索
                  1. ソースコード（全探索）
                  1. 処理の流れ
                  1. C言語
                  2. Python
                  1. (1) ナップサック問題とは
                  2. (2) ナップサック問題にチャレンジ！
                  3. (3) ナップサック問題のソースコード
                    1. C言語
                    2. Python