問題1：容量制約下での資料選択

この問題では、容量 N のナップサックに、異なる体積と価値を持つ M 種類のアイテムを詰め込むシナリオを想定します。各アイテムは1つずつしか選択できず、分割は不可能です。総価値を最大化するためのアイテムの組み合わせを求めます。

これは動的計画法における「0/1ナプサック問題」の標準的な出題形式です。2次元配列を用いた基本的なアプローチと、空間計算量を削減した1次元配列（ローリング配列）を用いたアプローチの2つの実装例を示します。

実装例：2次元DP配列による解法

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int itemTypes, bagCapacity;
    if (!(cin >> itemTypes >> bagCapacity)) return 0;

    vector<int> weights(itemTypes);
    vector<int> values(itemTypes);

    for (int i = 0; i < itemTypes; ++i) cin >> weights[i];
    for (int i = 0; i < itemTypes; ++i) cin >> values[i];

    // dpテーブル: dp[i][j] は i番目までのアイテムで容量jを実現した際の最大価値
    vector<vector<int>> dp(itemTypes + 1, vector<int>(bagCapacity + 1, 0));

    for (int i = 1; i <= itemTypes; ++i) {
        for (int j = 0; j <= bagCapacity; ++j) {
            int exclude = dp[i-1][j]; // アイテムを選ばない場合
            int include = 0;
            if (j >= weights[i-1]) {
                // アイテムを選ぶ場合
                include = dp[i-1][j - weights[i-1]] + values[i-1];
            }
            dp[i][j] = max(exclude, include);
        }
    }

    cout << dp[itemTypes][bagCapacity] << endl;
    return 0;
}

実装例：1次元配列による空間最適化

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int itemTypes, bagCapacity;
    cin >> itemTypes >> bagCapacity;

    vector<int> weights(itemTypes);
    vector<int> values(itemTypes);

    for (int i = 0; i < itemTypes; ++i) cin >> weights[i];
    for (int i = 0; i < itemTypes; ++i) cin >> values[i];

    // 1次元配列による最適化
    vector<int> dp(bagCapacity + 1, 0);

    for (int i = 0; i < itemTypes; ++i) {
        // 同一アイテムの重複使用を防ぐため、後ろから更新する
        for (int j = bagCapacity; j >= weights[i]; --j) {
            dp[j] = max(dp[j], dp[j - weights[i]] + values[i]);
        }
    }

    cout << dp[bagCapacity] << endl;
    return 0;
}

問題2：等和部分集合への分割

正の整数のみを含む配列 nums が与えられた場合、その配列を2つの部分集合に分割し、それぞれの要素の合計が等しくなるかどうかを判定します。

この問題は、配列の全要素の合計を sum としたとき、合計 sum / 2 を作成できるかという0/1ナプサック問題として帰着させることができます。

• ナップサックの容量： target = sum / 2
• アイテムの重みと価値： 配列の要素の値そのもの
• 目的： 容量 target をちょうど満たす選択が可能かどうかを判定する

配列の合計が奇数である場合、等和分割は不可能であるため即座に false を返します。

実装例：LeetCode 416

#include <vector>
#include <numeric>

using namespace std;

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int totalSum = accumulate(nums.begin(), nums.end(), 0);
        
        // 合計が奇数なら等分できない
        if (totalSum % 2 != 0) return false;
        
        int target = totalSum / 2;
        
        // dp[j] は合計 j を作成可能かどうかを示す真偽値
        vector<bool> dp(target + 1, false);
        dp[0] = true; // 合計0は常に可能
        
        for (int num : nums) {
            // 後ろから更新することで各要素を1回のみ使用する
            for (int j = target; j >= num; --j) {
                if (dp[j - num]) {
                    dp[j] = true;
                }
            }
        }
        
        return dp[target];
    }
};

• 時間計算量： O(n * target) ※ nは要素数、targetは合計の半分
• 空間計算量： O(target)