今日任务
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];
}
};
本站资源均来自互联网,仅供研究学习,禁止违法使用和商用,产生法律纠纷本站概不负责!如果侵犯了您的权益请与我们联系!
转载请注明出处: 免费源码网-免费的源码资源网站 » 代码随想录算法训练营Day35 | 01背包问题 | 416. 分割等和子集
发表评论 取消回复