0-1 背包问题(动态规划 查询背包元素)
描述
给定n种物品和一个背包,物品i的重量是Wi,其价值为Vi,问如何选择装入背包的物品,使得装入背包的物品的总价值最大?
在选择装入背包的物品时,对每种物品i只能有两种选择,装入或者不装入,不能装入多次,也不能部分装入。
输入描述
第一行输入物品的个数n。
第二行输入物品的重量序列w。(中间有空格)
第三行输入物品的价值序列v。(中间有空格)
第四行输入背包容量c。
输出描述
第一行输出装入背包的物品。(用0和1表示,中间无空格)
第二行输出最大价值。
用例输入 1
3 3 4 5 4 5 6 10
用例输出 1
011 11
提示:
n<100;
1<Wi,Vi<100;
本题是典型的背包问题,唯一的难点就是如何查询背包元素。
思路:
利用逆推发,反向查找,如果本像元素与上一列元素一样,则没装,否则装了,由此可推出以下代码:
string ans="";int W=c;for (int i=n;n>0 && s>0;i--){if (s==dp[i-1][W]) ans='0'+ans;else{ans='1'+ans;s-=v[i-1];W-=w[i-1];}}
则利用动态规划,将代码完善:
#include<bits/stdc++.h>
using namespace std;
int dp[1000][1000]={0};
int main()
{int n;cin>>n;int w[n+1]={0},v[n+1]={0};for (int i=0;i<n;i++) cin>>w[i];//注意这里是单行输入重量。for (int i=0;i<n;i++) cin>>v[i];//单行输入价值。int c;cin>>c; for (int i=1;i<=n;i++){for (int j=1;j<=c;j++){if (w[i-1]<=j) dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i-1]]+v[i-1]);//动态规划else (dp[i][j]=dp[i-1][j]);}}int s=dp[n][c];//开始逆推string ans="";int W=c;for (int i=n;n>0 && s>0;i--){if (s==dp[i-1][W]) ans='0'+ans;else{ans='1'+ans;s-=v[i-1];W-=w[i-1];}}int k=n-ans.size();while (k--) ans='0'+ans;//处理一下cout<<ans<<endl<<dp[n][c];//输出
}
相关文章:

0-1 背包问题(动态规划 查询背包元素)
描述 给定n种物品和一个背包,物品i的重量是Wi,其价值为Vi,问如何选择装入背包的物品,使得装入背包的物品的总价值最大? 在选择装入背包的物品时,对每种物品i只能有两种选择,装入或者不装入…...

elasticsearch快照生成与恢复
Elasticsearch快照生成与恢复的场景主要涉及到数据的备份与恢复需求。当需要对Elasticsearch集群中的数据进行备份,或者在数据丢失、损坏等情况下需要恢复数据时,就可以使用快照功能。 快照生成的方法通常包括以下步骤: 1、创建一个快照仓库…...

178.二叉树:最大二叉树(力扣)
代码解决 /*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* Tre…...

跨境电商中的IP隔离是什么?怎么做?
一、IP地址隔离的概念和原理 当我们谈论 IP 地址隔离时,我们实际上是在讨论一种网络安全策略,旨在通过技术手段将网络划分为不同的区域或子网,每个区域或子网都有自己独特的 IP 地址范围。这种划分使网络管理员可以更精细地控制哪些设备或用…...

【C++】stack、queue和deque的使用
💗个人主页💗 ⭐个人专栏——C学习⭐ 💫点击关注🤩一起学习C语言💯💫 目录 导读 一、stack 1. stack介绍 2. stack使用 二、queue 1. queue介绍 2. queue使用 三、deque 1. deque介绍 2. deque的…...

通过SSH远程登录华为设备
01 进入系统编辑视图 system-view Enter system view, return user view with return command. 02 创建本地RSA密钥对 [HUAWEI]rsa local-key-pair creat The key name will be:HUAWEI_Host The range of public key size is (2048 ~ 2048). NOTE: Key pair generation will ta…...

算法day27
第一题 515. 在每个树行中找最大值 首先是遍历每层的节点,将每一层最大值的节点的值保留下来,最后将所有层的最大值的表返回;具体的遍历每层节点的过程如上一篇故事; 综上所述,代码如下: /*** Definition …...

记录一次CTF图片拼图安装工具montage+gaps成功步骤以及踩坑全过程
安装图片拼接工具montage: 1.安装 使用pip install montage无法安装montage工具的师傅可以尝试下面的方法 #Debian apt-get install graphicsmagick-imagemagick-compat#Ubuntu apt-get install graphicsmagick-imagemagick-compat#Alpine apk add imagemagick6#…...

深入剖析人才管理的关键要素:“选、用、育、留”四大核心要素
在当今这个日新月异的商业时代,企业的成功不再仅仅取决于资金、技术或市场策略,而更多地依赖于企业所拥有的人才资源。有效的人才管理策略,尤其是“选、用、育、留”四大核心要素,已成为推动企业持续发展的关键。 一、选ÿ…...

【C++】类的默认成员函数
类的默认成员函数 类的六个默认成员函数构造函数构造函数的概念构造函数的特性 析构函数析构函数的概念析构函数的特性 构造函数与析构函数的调用顺序拷贝构造拷贝构造的概念拷贝构造的特性赋值运算符重载运算符重载赋值运算符重载前置与后置重载输入输出流重载 const修饰成员实…...

归并排序!
归并排序 https://articles.zsxq.com/id_g23e5o3lg87e.html 目录 归并排序算法思想命名由来算法描述sortList函数mergeSort函数 源代码 算法思想 通过将当前乱序的数组分成两个部分,分别进行「递归调用」,利用两个指针将数据元素以此比较,选…...

深入探讨:Spring与MyBatis中的连接池与缓存机制
深入探讨:Spring与MyBatis中的连接池与缓存机制 引言 在现代应用程序开发中,性能优化是一个永恒的话题。而在企业级Java应用开发中,Spring和MyBatis是两种非常流行的框架,它们的连接池和缓存机制对应用程序的性能有着至关重要的…...

[C#]使用C#部署yolov10的目标检测tensorrt模型
【测试通过环境】 win10 x64vs2019 cuda11.7cudnn8.8.0 TensorRT-8.6.1.6 opencvsharp4.9.0 .NET Framework4.7.2 NVIDIA GeForce RTX 2070 Super cuda和tensorrt版本和上述环境版本不一样的需要重新编译TensorRtExtern.dll,TensorRtExtern源码地址:T…...

Linux CFS 调度器 (1):概述
文章目录 1. 前言2. CFS 调度器2.1 概述2.2 一些实现细节2.3 运行队列:红黑树2.4 一些特征2.5 调度策略2.6 调度器类别2.7 扩展:组调度 3. 参考资料 1. 前言 限于作者能力水平,本文可能存在谬误,因此而给读者带来的损失ÿ…...

HBase中Master初始化错误~
ERROR:org.apache.hadoop.hbase.PleaseHoldException:Master is initializing 1、停止HBase运行 2、启动zookeeper中的zkCli.sh服务 ./zookeeper/bin/zkCli.sh 3、执行完毕显示以下结果,删除habse文件夹 4、重新启动HBase即可。...

Hive on Spark版本兼容性
Hive on Spark仅在特定版本的Spark上进行测试,因此给定版本的Hive只能保证与特定版本的Spark一起工作。其他版本的Spark可能与给定版本的Hive一起工作,但不能保证。以下是Hive版本及其对应的Spark版本列表: 详情参考官方文档:http…...

grep命令知多少
引言 1. grep命令的重要性 在Linux系统中,grep是一个不可或缺的文本处理工具,它允许用户快速搜索文件中的文本模式。这个命令的名称来源于Global Regular Expression Print,即全局正则表达式打印,它源自UNIX早期的ed文本编辑器。…...

[java]windows和linux下jdk1.8安装包所有版本系列下载地址汇总
【windows jdk1.9系列下载地址】 序号java版本下载地址1java-jdk9-jdk-9.0.1-windows-x64-bin.zip点我下载 【windows jdk1.8系列下载地址】 序号java版本下载地址1java-jdk1.8-jdk-8u202-windows-x64.zip点我下载2java-jdk1.8-jdk-8u201-windows-x64.zip点我下载3java-jdk1…...

Electron+Vue开源软件:洛雪音乐助手V2.8畅享海量免费歌曲
洛雪音乐助手是一款功能全面且完全免费的开源音乐软件,支持在Windows、Android和iOS平台上使用。 平台支持: 桌面版:采用Electron Vue技术栈开发,支持Windows 7及以上版本、Mac OS和Linux,具有广泛的用户群体覆盖。 …...

CAPL通过addTimeToMeasurementStartTime或者getLocalTime获取本地时间
文章目录 getLocalTimeaddTimeToMeasurementStartTimegetLocalTime long tm[9]; getLocalTime(tm); // now tm contains the following entries: // tm[0] = 3; (seconds) // tm[1] = 51; (minutes) // tm[2] = 16; (hours)...

谷歌上架,APP被移除了,没封号,换个包名还能重新提审上架?
对于在Google Play上架应用的开发者来说,尤其是那些矩阵式上架马甲包的开发者,可能已经遭遇过无数次应用被暂停或移除的情况了。通常这种情况下,账号也随之会被封,且大多数开发者认为,没有立马收到封号邮件的话&#x…...

Docker部署MaxKB 知识库(提高问答命中率)
前言 上一篇文章简单的介绍了下MaxKB,这一篇文章就讲如何部署MaxKB。 MaxKB实现逻辑也比较简单,如下图。 安装 修改Docker镜像源 由于不可抗力,部分源已经无法使用,需要修改以下的源地址来拉取镜像。如果是linux,…...

LeetCode739每日温度
题目描述 给定一个整数数组 temperatures ,表示每天的温度,返回一个数组 answer ,其中 answer[i] 是指对于第 i 天,下一个更高温度出现在几天后。如果气温在这之后都不会升高,请在该位置用 0 来代替。 解析 每次往栈中…...

【Qt】Qt中的几种Timer
1. QObject::startTimer int QObject::startTimer(int interval, Qt::TimerType timerType Qt::CoarseTimer) int QObject::startTimer(std::chrono::milliseconds time, Qt::TimerType timerType Qt::CoarseTimer)每次时间到了会调用虚函数timerEvent() 2. QTimer 3. QBa…...

Excel 多列组合内容循环展开
某表格 A 列是编号,其他列是用逗号分隔的意义不同的分类列 ABCDEFG1Assembly#ProductTypeUnit ConfigNominal CapacitySupply VoltageGenerationCase Construction23H1012290001CMD,P24,36FAA,B33H1012290002CMD,P48,60FA,BA,B43H1012290003CMD,P24,36B,C,D,EAA,B …...

Vue2+Element-ui实现el-table表格自适应高度
效果图 新建指令 Vue.directive(height, {inserted(el, _binding, vnode) {const paginationRef vnode.context.$refs.paginationRefconst calculateHeight () > {const windowHeight window.innerHeightconst topOffset el.getBoundingClientRect().topconst otherEle…...

【人工智能】开发AI可能获刑?加州1047草案详解
引言 随着人工智能(AI)技术的飞速发展,其应用领域不断扩展,但同时也引发了诸多争议和监管问题。近期,加州参议院以32比1的压倒性投票通过了1047号草案,又称《前沿人工智能模型安全可靠创新法案》。这一草案…...

机器学习二分类数据集预处理全流程实战讲解
本文概述 本文对weatherAUS数据集进行缺失值分析并剔除高缺失特征,合理填补剩余缺失值,利用相关性筛选关键特征,采用多种机器学习模型(如逻辑回归、随机森林等)在80%训练集上训练,并在20%测试集上预测明日降…...

大模型应用:LangChain-Golang核心模块使用
1.简介 LangChain是一个开源的框架,它提供了构建基于大模型的AI应用所需的模块和工具。它可以帮助开发者轻松地与大型语言模型(LLM)集成,实现文本生成、问答、翻译、对话等任务。LangChain的出现大大降低了AI应用开发的门槛,使得任何人都可以…...

【Tkinter界面】Canvas 图形绘制(03/5)
文章目录 一、说明二、画布和画布对象2.1 画布坐标系2.2 鼠标点中画布位置2.3 画布对象显示的顺序2.4 指定画布对象 三、你应该知道的画布对象操作3.1 什么是Tag3.2 操作Tag的函数 https://www.cnblogs.com/rainbow-tan/p/14852553.html 一、说明 Canvas(画布&…...