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;
}
};