46.研究材料の持ち運び問題 動的計画法を用いたナップサック問題の解法について解説する。`dp`配列を定義し、`dp[i][j]`はi個の物品をjの容量で運ぶ際の最大価値を表す。漸化式は以下の2つのケースに分けられる： 1. 物品を入れられる場合：`dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]]+value[i])` 2. 物品を入れられない場合：`dp[i][j] = dp[i-1][j]` 初期化処理では、容量0の場合は価値0、物品1つの場合はその物品の価値で初期化する。

#include<iostream>
#include<vector>
using namespace std;

int solveKnapsack(int items, int capacity, vector<int>& weights, vector<int>& values) {
    vector<vector<int>> dp(items, vector<int>(capacity+1, 0));
    
    for(int c = weights[0]; c <= capacity; c++) {
        dp[0][c] = values[0];
    }
    
    for(int i = 1; i < items; i++) {
        for(int c = 0; c <= capacity; c++) {
            if(c < weights[i]) {
                dp[i][c] = dp[i-1][c];
            } else {
                dp[i][c] = max(dp[i-1][c], dp[i-1][c-weights[i]] + values[i]);
            }
        }
    }
    return dp[items-1][capacity];
}

int main() {
    int itemCount, maxCapacity;
    cin >> itemCount >> maxCapacity;
    
    vector<int> weights(itemCount);
    vector<int> values(itemCount);
    
    for(int i = 0; i < itemCount; i++) cin >> weights[i];
    for(int i = 0; i < itemCount; i++) cin >> values[i];
    
    cout << solveKnapsack(itemCount, maxCapacity, weights, values) << endl;
    return 0;
}

空間最適化版（1次元配列使用）:

#include<iostream>
#include<vector>
using namespace std;

int optimizedKnapsack(int items, int capacity, vector<int>& weights, vector<int>& values) {
    vector<int> dp(capacity+1, 0);
    
    for(int i = 0; i < items; i++) {
        for(int c = capacity; c >= weights[i]; c--) {
            dp[c] = max(dp[c], dp[c-weights[i]] + values[i]);
        }
    }
    return dp[capacity];
}

416.等和分割問題 配列を和が等しい2つの部分集合に分割可能か判定する問題。総和が奇数なら不可、偶数なら目標値を総和の半分としてナップサック問題と同様に解く。

class Solution {
public:
    bool canDivideEqually(vector<int>& nums) {
        int total = accumulate(nums.begin(), nums.end(), 0);
        if(total % 2 != 0) return false;
        
        int target = total / 2;
        vector<bool> dp(target+1, false);
        dp[0] = true;
        
        for(int num : nums) {
            for(int i = target; i >= num; i--) {
                dp[i] = dp[i] || dp[i-num];
            }
        }
        return dp[target];
    }
};