代码随想录算法训练营第41天 [01背包的理论基础，二维数组解法，一维数组解法，416. 分割等和子集]

代码随想录算法训练营第41天 [01背包的理论基础，二维数组解法，一维数组解法，416. 分割等和子集]

一、01背包的二维数组解法

链接: 代码随想录.
思路：dp数组, dp[i][j]代表行李箱空间为j的情况下,从下标为[0, i]的物品里面任意取,能达到的最大价值，递推公式为 dp[i][j] = max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i])
做题状态：看解析后做出来了

//二维dp数组实现
#include <bits/stdc++.h>
using namespace std;

int n, bagweight;// bagweight代表行李箱空间


void solve() {
    vector<int> weight(n, 0); // 存储每件物品所占空间
    vector<int> value(n, 0);  // 存储每件物品价值
    for(int i = 0; i < n; ++i) {
        cin >> weight[i];
    }
    for(int j = 0; j < n; ++j) {
        cin >> value[j];
    }
    // dp数组
    // dp[i][j]代表行李箱空间为j的情况下,从下标为[0, i]的物品里面任意取,能达到的最大价值
    vector<vector<int>> dp(n,vector<int>(bagweight+1,0));
    for(int j = 0 ;j<=bagweight;j++){
        if(j >= weight[0]){
            dp[0][j] = value[0];
        }
    }


    for(int i = 1;i<n;i++){
        for(int j = 0;j<=bagweight;j++){
            if(weight[i]>j){
                dp[i][j] = dp[i-1][j];
            }else{
                dp[i][j] = max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i]);
            }
        }
    }

    cout << dp[n-1][bagweight] <<endl;
}


int main() {
    while(cin >> n >> bagweight) {
        solve();
    }
    return 0;
}

二、01背包的一维数组解法

链接: 代码随想录.
思路：
一维数组实现 dp数组的含义 dp[j] 在背包大小为j时的最大价值
二维数组的递推公式为 dp[i][j] = max(dp[i-1][j],dp[i-1][j-weight[i]+value[i])
一维数组的递推公式为 dp[j] = max(dp[j],dp[j-weight[i]+value[i])
一维数组的解法里，必须先遍历物品，再遍历背包
并且遍历背包的时候必须时倒序
j代表空间，空间必须比我选择的物品i的容量要大，所以时j>=weight[i]
做题状态：看解析后做出来了

//二维dp数组实现
#include <bits/stdc++.h>
using namespace std;

int n, bagweight;// bagweight代表行李箱空间


void solve() {
    vector<int> weight(n, 0); // 存储每件物品所占空间
    vector<int> value(n, 0);  // 存储每件物品价值
    for(int i = 0; i < n; ++i) {
        cin >> weight[i];
    }
    for(int j = 0; j < n; ++j) {
        cin >> value[j];
    }
    //一维数组实现 dp数组的含义 dp[j] 在背包大小为j时的最大价值
    //二维数组的递推公式为 dp[i][j] = max(dp[i-1][j],dp[i-1][j-weight[i]+value[i])
    //一维数组的递推公式为 dp[j] = max(dp[j],dp[j-weight[i]+value[i])
    vector<int> dp(bagweight+1,0);
    //一维数组的解法里，必须先遍历物品，再遍历背包
    //并且遍历背包的时候必须时倒序
    
    //j代表空间，空间必须比我选择的物品i的容量要大，所以时j>=weight[i]
    for(int i = 0;i<n;i++){
        for(int j = bagweight;j>=weight[i];j--){
            dp[j] = max(dp[j],dp[j-weight[i]]+value[i]);
        }
    }
    cout << dp[bagweight] <<endl;
}


int main() {
    while(cin >> n >> bagweight) {
        solve();
    }
    return 0;
}

三、416. 分割等和子集

链接: 代码随想录.
思路：把问题转化为01背包，
相当于从nums里取数，重量 = 价值 = 数值
有一个大小为target的背包，能不能将背包装满
做题状态：看解析后做出来了

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        vector<int> dp(10001, 0);
        int sum = 0;
        for (int n : nums) {
            sum += n;
        }
        if (sum % 2 == 1) {
            return false;
        }
        int target = sum / 2;
        // 相当于从nums里取数，重量 = 价值 = 数值
        // 有一个大小为target的背包，能不能将背包装满
        for (int i = 0; i < nums.size(); i++) {
            for (int j = target; j >= nums[i]; j--) {
                dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
            }
        }

        return dp[target] == target;
    }
};