動的計画法（DP）演習問題 #C++ – Qiita

// 問題2: ナップサック問題
// 問題文
// N個のアイテムがあり、各アイテムには価値(value)と重さ(weight)があります。あなたは最大容量Wのナップサックを持っています。ナップサックに入れる品物を選んで、価値の合計が最大になるようにしてください。ただし、各アイテムは1つずつしかありません。

#include 
#include 
#include 
using namespace std;

int knapsack(vectorint>& weights, vectorint>& values, int W) {
  int n = weights.size();

  // 2次元配列（二次元ベクター）を宣言して全ての要素を0で初期化
  // + 1　はベースケース
  // dp[0][w] というベースケース（何も選ばない初期状態）を表現するために、配列のサイズを n+1 に。
  // 容量 0 のケースも考慮するため、配列のサイズは W+1 になります。
  vectorvectorint>> dp(n + 1, vectorint>(W + 1, 0));

  for (int i = 1; i  n; i++) {
        for (int w = 0; w  W; w++) {
            if (weights[i-1]  w) {
                // アイテムを選ぶか選ばないかの最大値
                dp[i][w] = max(dp[i-1][w], dp[i-1][w - weights[i-1]] + values[i-1]);
            } else {
                // アイテムが容量を超える場合は選べない
                dp[i][w] = dp[i-1][w];
            }
        }
    }

    return dp[n][W];
}


int main() {
  vectorint> weights = {2, 3, 4, 5};
  vectorint> values = {3, 4, 5, 6};
  int W = 8;

  cout  "ナップサックの最大価値: "  knapsack(weights, values, W)  endl; // => ナップサックの最大価値: 10

  return 0;
}

// ナップサック問題の基本概念
// ナップサック問題は「限られた容量の中で最大の価値を持つ品物の組み合わせを選ぶ」という最適化問題です。この問題では、各アイテムを「選ぶ」か「選ばない」かの二択があります。

// DPテーブルの構造と意味
// vector> dp(n + 1, vector(W + 1, 0));
// ここで作成している2次元配列 dp[i][w] の意味は：
// - i: 0からi-1番目までのアイテムだけを考慮した場合
// - w: ナップサックの容量がwの場合
// - dp[i][w]: その条件下での最大価値
// 特に注意すべきは、dp[i][w]のiは実際のアイテムインデックスより1大きくなっています。これはDPテーブルの初期状態（何も選ばない状態）をdp[0][w] = 0として表現するためです。

// アルゴリズムのステップ
// 1. 初期化: dp[0][w] = 0 for all w (アイテムを何も選ばない場合は価値も0)

// 2. DPテーブルの埋め方:
// for (int i = 1; i 
//     for (int w = 0; w 
//         if (weights[i-1] 
//             // アイテムを選ぶか選ばないかの最大値
//             dp[i][w] = max(dp[i-1][w], dp[i-1][w - weights[i-1]] + values[i-1]);
//         } else {
//             // アイテムが容量を超える場合は選べない
//             dp[i][w] = dp[i-1][w];
//         }
//     }
// }

// この部分で各ステップごとに以下のことを考えています：
// - weights[i-1] 
//     - dp[i-1][w]: i-1番目のアイテムまでを考慮し、このアイテム（i-1番目）を「選ばない」場合の最大価値
//     - dp[i-1][w - weights[i-1]] + values[i-1]: i-1番目のアイテムまでを考慮し、このアイテムを「選ぶ」場合の最大価値
//     - これらの大きい方を選びます
// - weights[i-1] > w: 現在のアイテムが容量に収まらない場合
//     - このアイテムは選べないので、前の状態（i-1番目までのアイテムを考慮した最大価値）をそのまま使います

// 3. 最終結果: dp[n][W] が求める答え（全てのアイテムを考慮して容量Wの制限内での最大価値）です

// 具体例での動作
// 例として、以下のデータで考えます：
//  - アイテム: [(重さ2, 価値3), (重さ3, 価値4), (重さ4, 価値5), (重さ5, 価値6)]
//  - ナップサック容量: W = 8

// DP表を埋めていく過程を追ってみましょう：
// 1. 初期状態:
//    - dp[0][w] = 0 for all w (アイテムを何も選ばない場合)
// 2. i=1（最初のアイテム：重さ2, 価値3）の場合:
//    - w 
//    - w ≥ 2: 選ぶか選ばないかの最大値 → dp[1][w] = max(0, 0 + 3) = 3
// 3. i=2（2番目のアイテム：重さ3, 価値4）の場合:
//    - w 
//    - w ≥ 3: 選ぶか選ばないかの最大値
//       - 例えば、w=5の場合: dp[2][5] = max(dp[1][5], dp[1][5-3] + 4) = max(3, 3 + 4) = 7
// 4. 以降も同様に計算し、最終的に dp[4][8] を求めます。

// 例として一部のDP表の値を示すと：
//    - dp[1][2] = 3: 最初のアイテムだけで容量2の場合、価値3が最大
//    - dp[2][5] = 7: 最初と2番目のアイテムまでで容量5の場合、価値7が最大（両方選んだ場合）
//    - dp[4][8] = 10: 全てのアイテムを考慮して容量8の場合、価値10が最大