leetcode打卡#day43 携带研究材料（第六期模拟笔试）、416. 分割等和子集

携带研究材料（第六期模拟笔试）

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

using namespace std;

int getMaxValue(vector<int>& weights, vector<int>& values, int n, int m) {
    vector<vector<int>> dp(n, vector<int>(m+1, 0));
    //初始化
    for (int j = weights[0]; j <= m; j++) {
        dp[0][j] = values[0];
    }
    for(int i = 1; i < n; i++) { // 遍历物品
        for(int j = 1; j <= m; j++) { // 遍历背包容量
            if (j < weights[i]) dp[i][j] = dp[i - 1][j];
            else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weights[i]] + values[i]);
    
        }
    }
    return dp[n-1][m];
}

int main() {
    int n, m; // n: 材料种类， m: 行李箱的容量
    cin >> n >> m;
    vector<int> weights(n);
    vector<int> values(n);
    for (int i = 0; i < n; i++) {
        cin >> weights[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> values[i];
    }
    int result = getMaxValue(weights, values, n, m);
    cout << result;
}

416. 分割等和子集

class Solution {
public:
 //背包问题（0-1）用不了二维数组
 bool canPartition(vector<int>& nums) {
    int n = nums.size();
    //dp[i] 容量为i的最大价值
    vector<int> dp(10001, 0);
    //int sum = 0;  
    //for (int i = 0; i < n; i++)  sum += nums[i];
    int sum = accumulate(nums.begin(), nums.end(), 0);
    if (sum % 2 == 1) return false;
    int target = sum/2;

    //遍历
    for (int i = 1; i < n; i++){
        //每个元素只可以遍历一次
        for (int j = target; j >= nums[i]; j--){
            dp[j] = max(dp[j], dp[j-nums[i]] + nums[i]);
        }
    }
    if (dp[target] == target) return true;
    return false;
}
};