代码随想录算法训练营Day35 | 01背包问题 | 416. 分割等和子集

今日任务

01背包问题

• 题目链接： https://kamacoder.com/problempage.php?pid=1046
• 题目描述：
  

Code

#include <iostream>
#include <vector>
#include <functional>
#include <algorithm>using namespace std;int main(void){int n, sz;cin >> n >> sz;vector<int> spaces(n);vector<int> values(n);for(int i = 0; i < n; i++){cin >> spaces[i];}for(int i = 0; i < n; i++){cin >> values[i];}// dp[i][c] = max(dp[i - 1][c], dp[i - 1][c - spaces[i]] + values[i]);vector<int> dp(sz + 1);for(int i = 0; i < n; i++){int x = spaces[i], v = values[i];for(int c = sz; c >= x; c--){dp[c] = max(dp[c], dp[c - x] + v);}}cout << dp[sz] << "\n";return 0;
}

416. 分割等和子集

• 题目链接： https://leetcode.cn/problems/partition-equal-subset-sum/
• 题目描述：
  

Code

class Solution {
public:bool canPartition(vector<int>& nums) {int sum = reduce(nums.begin(), nums.end(), 0);if(sum % 2){return false;}int t = sum / 2;int n = nums.size();// vector<vector<int>> memo(n, vector<int>(t + 1, -1));// function<bool(int, int)> dfs = [&](int i, int c)->bool{//     if(i < 0){//         return c == 0;//     }//     int &res = memo[i][c];//     if(res != -1){//         return res;//     }//     // if(c < nums[i]){//     //     return res = dfs(i - 1, c);//     // }//     // return res = dfs(i - 1, c) || dfs(i - 1, c - nums[i]);//     return res = c >= nums[i] && dfs(i - 1, c - nums[i]) || dfs(i - 1, c);// };// return dfs(n - 1, t);// vector<vector<bool>> dp(n + 1, vector<bool>(t + 1));// dp[0][0] = true;// for(int i = 0; i < n; i++){//     int x = nums[i];//     for(int c = 0; c <= t; c++){//         dp[i + 1][c] = c >= x && dp[i][c - x] || dp[i][c];//     }// }// return dp[n][t];vector<bool> dp(t + 1);dp[0] = true;int pre = 0;for(int x : nums){pre = min(pre + x, t);for(int c = pre; c >= x; c--){dp[c] = dp[c] || dp[c - x];}}return dp[t];}
};