小米笔试题——01背包问题变种

在这里插入图片描述
这段代码的主要思路是使用动态规划来构建一个二维数组 dp,其中 dp[i][j] 表示前 i 个产品是否可以组合出金额 j。通过遍历产品列表和可能的目标金额,不断更新 dp 数组中的值,最终返回 dp[N][M] 来判断是否可以组合出目标金额 M。如果 dp[N][M] 为 true,则表示可以组合出目标金额,否则表示无法组合出目标金额。

#include <iostream>
#include <vector>
#include <limits>using namespace std;bool miHomeGiftBag(vector<int> p, int M) {int N = p.size(); // 获取产品列表中产品的数量vector<vector<bool>> dp(N + 1, vector<bool>(M + 1, false)); // 创建一个二维动态规划数组,dp[i][j] 表示前 i 个产品是否能够组合出金额 jdp[0][0] = true; // 初始化,金额为0时总是可以组合出来for (int i = 1; i <= N; i++) { // 遍历产品列表for (int j = 0; j <= M; j++) { // 遍历可能的目标金额dp[i][j] = dp[i - 1][j]; // 初始情况,不使用当前产品 iif (j - p[i - 1] >= 0) { // 如果当前目标金额 j 大于等于当前产品的价格// 尝试使用当前产品 i,判断前 i-1 个产品是否可以组合出目标金额 j - p[i-1]dp[i][j] = dp[i - 1][j - p[i - 1]] || dp[i][j];}}}return dp[N][M]; // 返回 dp[N][M],表示前 N 个产品是否可以组合出目标金额 M
}int main() {bool res;int _p_size = 0;cin >> _p_size;cout << _p_size << endl;vector<int> _p;int _p_item;for(int _p_i=0; _p_i<_p_size; _p_i++) {cin >> _p_item;cin.ignore (std::numeric_limits<std::streamsize>::max(), '\n');_p.push_back(_p_item);}int _M;cin >> _M;cin.ignore (std::numeric_limits<std::streamsize>::max(), '\n');res = miHomeGiftBag(_p, _M);cout << res << endl;return 0;}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/139130.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Android studio安卓生成APK文件安装包方法

1.点击Build->Generate Signed Bundle/APK 2.选择APK 3.首次生成&#xff0c;没有jks文件&#xff0c;就点击Create new。再次生成&#xff0c;直接点Next 4.选择创建jks文件路径 5.点击Next 6.选择release 7.生成完成的apk安装包路径

【论文阅读 08】Adaptive Anomaly Detection within Near-regular Milling Textures

2013年&#xff0c;太老了&#xff0c;先不看 比较老的一篇论文&#xff0c;近规则铣削纹理中的自适应异常检测 1 Abstract 在钢质量控制中的应用&#xff0c;我们提出了图像处理算法&#xff0c;用于无监督地检测隐藏在全局铣削模式内的异常。因此&#xff0c;我们考虑了基于…

uniapp小程序点击按钮直接退出小程序效果demo(整理)

点击按钮直接退出小程序 <navigator target"miniProgram" open-type"exit">退出小程序</navigator>

Android Key/Trust Store研究+ssl证书密钥

前言&#xff1a;软件搞环境涉及到了中间件thal trustzone certificate key&#xff0c;翻译过来是thal信任区域证书密钥 &#xff0c;不明白这是什么&#xff0c;学习一下 ssl证书密钥 SSL密钥是SSL加密通信中的重要组成部分。SSL证书通过加密算法生成&#xff0c;用于保护网…

Oracle 11g RAC部署笔记

搭了三次才搭好&#xff0c;要记录一下。 1. Oracle 11g RAC部署的相关步骤以及需要的包&#xff0c;可以参考这里。 Oracle 11g RAC部署_12006142的技术博客_51CTO博客Oracle 11g RAC部署&#xff0c;Oracle11gRAC部署操作环境&#xff1a;CentOS7.4Oracle11.2.0.4一、主机网…

解决老版本Oracle VirtualBox 此应用无法在此设备上运行问题

问题现象 安装华为eNSP模拟器的时候&#xff0c;对应的Oracle VirtualBox-5.2.26安装的时候提示兼容性问题&#xff0c;无法进行安装&#xff0c;具体版本信息如下&#xff1a; 软件对应版本备注Windows 11专业工作站版22H222621eNSP1.3.00.100 V100R003C00 SPC100终结正式版…

利用优化算法提高爬虫任务调度效率

目录 一、任务调度优化的重要性 二、选择合适的优化算法 三、建立任务调度模型 四、设计适应性函数 五、算法实施和调优 六、性能评估和优化结果分析 代码示例 总结 随着网络信息的爆炸式增长&#xff0c;网络爬虫在信息获取和数据挖掘等领域的应用越来越广泛。然而&am…

Arduino程序设计(十一)8×8 共阳极LED点阵显示(74HC595)

88 共阳极LED点阵显示 前言一、74HC595点阵模块1、74HC595介绍2、74HC595工作原理3、1088BS介绍4、74HC595点阵模块 二、点阵显示实验1、点阵显示初探2、点阵显示进阶3、点阵显示高阶3.1 点阵显示汉字&#xff08;方法1&#xff09;3.2 点阵显示汉字&#xff08;方法2&#xff…

conda的安装和使用

参考资料&#xff1a; https://www.bilibili.com/read/cv8956636/?spm_id_from333.999.0.0 https://www.bilibili.com/video/BV1Mv411x775/?spm_id_from333.999.0.0&vd_source98d31d5c9db8c0021988f2c2c25a9620 目录 conda是啥以及作用conda的安装conda的启动conda的配置…

2023华为杯D题——基于Kaya模型的碳排放达峰实证研究

一、前言 化石能源是推动现代经济增长的重要生产要素&#xff0c;经济生产活动与碳排放活动密切相关。充分认识经济增长与碳排放之间的关系对转变生产方式&#xff0c;确定碳达峰、碳中和路径极为必要。本研究在对经济增长与碳排放关系现有研究梳理的基础上&#xff0c;系统地分…

【二叉树魔法:链式结构与递归的纠缠】

本章重点 二叉树的链式存储二叉树链式结构的实现二叉树的遍历二叉树的节点个数以及高度二叉树的创建和销毁二叉树的优先遍历和广度优先遍历二叉树基础oj练习 1.二叉树的链式存储 二叉树的链式存储结构是指&#xff0c;用链表来表示一棵二叉树&#xff0c;即用链来指示元素的逻辑…

23. 图论 - 图的由来和构成

文章目录 图的由来图的构成Hi, 你好。我是茶桁。 从第一节课上到现在,我基本上把和人工智能相关的一些数学知识都教给大家了,终于来到我们人工智能数学的最后一个部分了,让我们从今天开始进入「图论」。 图论其实是一个比较有趣的领域,因为微积分其实更多的是对应连续型的…

iOS——KVC(键值编码)

键值编码&#xff08;KVC&#xff09; KVC&#xff08;Key Value Coding&#xff09;是一种允许以字符串形式间接操作对象属性的方式。 最基本的KVC是由NSKeyValueCoding协议提供支持&#xff0c;最基本的操作属性如下&#xff1a; setValue: 属性值 forKey: 属性名&#xff…

微信小程序之项目基本结构、页面的基础及宿主环境

文章目录 前言一、基本组成结构基本组成小程序页面的组成部分JSON配置文件作用 二、页面基础pagesWXML和HTML的区别WXSS和CSS的区别小程序中js文件分类 三、小程序宿主环境总结 前言 微信小程序的项目基本结构、页面的基础及宿主环境 一、基本组成结构 基本组成 新建一个微信…

迁移 MySQL 数据到 OceanBase 集群

使用 mysqldump 将 mysql的表结构和数据同步到 OceanBase 的MySQL 租户中 Mysql数据库导出 mysqldump -h127.0.0.1 -P3306 -uroot –p --single-transaction --hex-blob --routines --events --triggers --set-gtid-purgedOFF --databases teller >teller.sql mysql> …

网络编程day05(IO多路复用)

今日任务&#xff1a; TCP多路复用的客户端、服务端&#xff1a; 服务端代码&#xff1a; #include <stdio.h> #include <sys/types.h> #include <sys/socket.h> #include <arpa/inet.h> #include <netinet/in.h> #include <unistd.h> …

网络隔离下实现的文件传输,现有的方式真的安全吗?

在当今的信息化时代&#xff0c;网络安全已经成为了各个企业和机构不可忽视的问题。为了保护内部数据和系统不受外部网络的攻击和泄露&#xff0c;一些涉及国家安全、商业机密、个人隐私等敏感信息的企业和机构&#xff0c;通常会对内外网进行隔离&#xff0c;即建立一个独立的…

Xilinx FPGA 7系列 GTX/GTH Transceivers (4) Aurora 8b10b 递增数收发验证

第一节:Xilinx FPGA 7系列 GTX/GTH Transceivers (1)–了解了GTX硬件的基础知识 第二节:IBERT GTX --通过Ibert IP测试链路通信 第三节:aurora 8b10b single lane 4byte–学习官方历程 递增数验证 自行编写data_gen和data_check 验证aurora 8b10b SFP 1.25G 收发正确。 组…

CentOS在应用程序菜单中创建快捷方式

背景&#xff1a; 在CentOS系统中&#xff0c;安装一些应用软件的时候&#xff0c;我们可能会自定义安装路径&#xff1b;这样在安装完应用程序后&#xff0c;在“Application”下&#xff0c;可能找不到对应的快捷键&#xff1b;这是就需要手动去创建跨界方式。 应用&#xf…

CNN(九):Inception v3算法实战

&#x1f368; 本文为&#x1f517;365天深度学习训练营 中的学习记录博客 &#x1f356; 原作者&#xff1a;K同学啊|接辅导、项目定制 1 理论基础 Inception v3论文 Inception v3由谷歌研究员Christian Szegedy等人在2015年的论文《Rethinking the Inception Architecture f…