当前位置: 首页 > news >正文

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;
}
};
http://www.lryc.cn/news/374032.html

相关文章:

  • MPLS的配置
  • 【机器学习】机器学习与教育科技在个性化教学中的融合应用与性能优化新探索
  • C++:十大排序
  • Python武器库开发-武器库篇之Mongodb未授权漏洞扫描器(五十六)
  • 【论文速读,找找启发点】2024/6/16
  • canal监控mysql变化
  • MySQLWorkbench导出sql文件
  • 不一样的SYSTEM APP(SYSTEM flag和system_prop区别)
  • C++ 和 JAVA 位运算符
  • 项目进度和成本管理
  • Dorkish:一款针对OSINT和网络侦查任务的Chrome扩展
  • 树莓派4B_OpenCv学习笔记10:调整视频帧大小
  • MySQL 保姆级教程(五):数据过滤
  • 《全职猎人》
  • Linux各目录的作用
  • Windows Docker Desktop 安装 postgres
  • C# OpenCvSharp Mat操作-创建Mat-构造函数
  • 【制作100个unity游戏之29】使用unity复刻经典游戏《愤怒的小鸟》(完结,附带项目源码)
  • 稀疏矩阵是什么 如何求
  • 57.Linux/Unix 系统编程手册(下) -- SOCKET : Unix domain
  • Hvv--知攻善防应急响应靶机--Linux1
  • Solus Linux: 有自己的软件包管理器
  • Java GUI编程
  • ROS机器人小车建模仿真与SLAM
  • Windows10安装Docker Desktop(实操步骤版)
  • Leetcode 45. 跳跃游戏 II(DP 双指针)
  • Codeforces Round 952 (Div. 4)(实时更新)
  • 【AI实践】Dify开发应用和对接微信
  • 精准定位,智慧提纯:高级数据提取策略
  • USB转I2C转SPI芯片CH341与CH347比较