今日任务
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];}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<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];}
};
