46.携带研究材料

二维数组

题目链接 文章讲解 视频讲解

动态规划五部曲：

1. dp[i][j]：下标i表示背包装0-i的物品(任取),j表示当前背包的最大容量，dp[i][j]表示容量为j时，装0-i的物品的最大价值
2. 递推公式：dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i])
   • dp[i-1][j] 表示j的容量全部装0-i-1的物品，不装物品i的最大价值
   • dp[i-1][j-weight[i]] 表示背包空出装物品i的容量的最大价值，再加上value[i]，表示容量为j时，装物品j的最大价值
   • 两者取最大值，就是dp[i][j]的最大价值，如果不装i价值最大，则取前者；如果装物品i价值最大，则取后者
3. 初始化：
   • 由递推公式可以看出dp[i][j]取决于左面和和上面的最大值
   • 当背包容量为0时，最大价值都为0:

   for(int row = 0; row < M; ++row) {
       dp[row][0] = 0;
   }
   

   • 当背包只装物品0时，最大价值取决去背包是否能装下物品0

   for(int col = weights[0]; col <= N; ++col) {
       dp[0][col] = value[0];
   }
   

4. 遍历顺序：由于dp[i][j]取决于dp[i-1][j]和dp[i-1][j-weight[i]] + value[i]所以先遍历背包和先遍历物品都可以
5. 打印dp数组

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


int main() {
    
    int M, N;
    cin >> M >> N;
    // dp[i][j] 表示：下标为[0-i]的物品任取，放进容量为j的背包，价值最大是多少
    vector<vector<int>> dp(M, vector<int>(N+1, 0));
    vector<int> weights;
    vector<int> value(M);
    for(int i = 0; i < M; ++i) {
        int weight;
        cin >> weight;
        weights.push_back(weight);
    }

    for(int i = 0; i < M; ++i) {
        cin >> value[i];
    }
    
    
    // 递推公式dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i]] + value[i])
    
    // 初始化
    for(int row = 0; row < M; ++row) {
        dp[row][0] = 0;
    }
    for(int col = weights[0]; col <= N; ++col) {
        dp[0][col] = value[0];
    }
    
    for(int cap = 1; cap <= N; ++cap) {
        for(int item = 1; item <M; ++item) {
            if(cap < weights[item]) dp[item][cap] = dp[item-1][cap];
            else dp[item][cap] = max(dp[item-1][cap], (dp[item-1][cap-weights[item]] + value[item]));
        }
    }

    
    cout << dp[M-1][N];    

    return 0;
}

滚动数组

文章讲解 视频讲解
动态规划五部曲：

1. dp[j]：容量为j的背包所能装物品的最大价值
2. 递推公式：dp[j] = max(dp[j], dp[j-weights[i] + value[i])
3. 初始化：由递推公式可知，dp数组每一次更新都依赖于本身的值，所以本身的值在初始化时不应过大，使得dp数组无法更新，所以初始化为0即可
4. 遍历顺序：先遍历物品后遍历背包，且背包必须倒序遍历；、
   • 背包为什么要倒序遍历：
     递推公式dp[j-weight[i]] + value[i],由于j >= j - weight[i] 所以背包从小到大遍历dp[j - weighs[i]]这个值已经填过了，会影响到dp[j]；试想dp[2] = dp[2-1] + value[1] 相当于将两个物品1装入了背包
   • 为什么先遍历物品：
     dp[j] = dp[j-weights[i] + value[i], 首先遍历最大容量的背包，此时并没有物品已经装入，是一个空的背包，所以j-weights[i] <= j的值全是0,这样相当于将所有物品放进取试一下装哪一个价值最大，结束后，背包将只装有一个物品
5. 打印dp数组

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


int main() {
    
    int M, N;
    cin >> M >> N;
    
    vector<int> weights(M);
    vector<int> value(M);
    
    for(int i = 0; i < M; ++i) cin >> weights[i];
    for(int i = 0; i < M; ++i) cin >> value[i];
    
    
    // dp[j]: 容量为j时，dp数组的最大价值
    vector<int> dp(N + 1);
    
    // 递推公式dp[j] = max(dp[j], dp[j-weights[i]] + value[i])
    
    // 初始化
    for(int j = 0; j < N; ++j) {
        dp[j] = 0;
    }
    
    // 遍历顺序
    for(int i = 0; i < M; ++i) {
        for(int j = N; j >=0; --j) {
            if(j < weights[i]) continue;
            else dp[j] = max(dp[j], dp[j-weights[i]] + value[i]);
        }
    }
    // for(int i = 0; i < N; ++i) cout << dp[i];
    
    cout << dp[N];

    return 0;
}

416.分割等和子集

题目链接 文章讲解 视频讲解

问题抽象：物品i的重量nums[i], 价值也是nums[i]

• dp[j]: 当前子集的和
• 递推公式：p[j] = max(dp[j], dp[j-nums[i]] + nums[i]);
• 初始化：默认初始化为0
• 遍历顺序：先遍历物品，再遍历背包；背包倒序遍历
• 打印dp数组

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int target = 0;
        for(int val : nums) target += val;
        if(target % 2 == 1) return false;
        target = target >> 1;
        
        vector<int> dp(target + 1, 0);

        for(int i = 0; i < nums.size(); ++i) {
            for(int j = target; j >= 0; --j) {
                if(j < nums[i]) continue;
                else dp[j] = max(dp[j], dp[j-nums[i]] + nums[i]);
            }
        }
        return dp[target] == target;
    }
};