PTA 7-2 0/1背包问题(回溯法) 作者 王东 单位 贵州师范学院
0/1背包问题。给定一载重量为W的背包及n个重量为wi、价值为vi的物体,1≤i≤n,要求重量和恰好为W具有最大的价值。
输入格式:
第一行输入背包载重量W及背包个数n,再依次输入n行,每行为背包重量wi和价值vi。
输出格式:
第一行输出装入背包内的物体编号(末尾有空格),若没有任何物品能装入,输出: No,第二行输出背包内的物体总价值。
输入样例1:
5 10
2 6
2 3
6 5
5 4
4 6
输出样例1:
1 2 3
14
输入样例2:
2 10
11 2
13 100
输出样例2:
No
0
学校老师给的题目与网上有一点偏差,但区别不大。
本题思路参考自这篇文章:7-12 0/1背包问题 (30 分)_给定一载重量为w的背包及n个重量为wi、价值为vi的物体,1≤i≤n,要求而且重量和恰-CSDN博客
修改后符合本题的代码如下:
#include <bits/stdc++.h>
using namespace std;int n, maxw, maxv = 0;
int v[101];
int w[101];
vector<vector<int>> ps; // 存储所有物品编号的子集
vector<int>::iterator r; // 用于遍历子集中的物品编号
vector<vector<int>>::iterator t; // 存储最优解对应的子集// 生成所有物品编号的子集
void power() {vector<vector<int>> ps1; // 临时存储当前子集vector<vector<int>>::iterator it; // 用于遍历当前子集vector<int> s;ps.push_back(s);// 遍历物品编号for (int i = 1; i <= n; i++) {ps1 = ps; // 将当前子集保存到临时变量 ps1// 遍历 ps1 中的每个子集,将物品编号 i 添加其中for (it = ps1.begin(); it != ps1.end(); it++) {(*it).push_back(i); // 向子集中添加物品编号i}// 将扩展后的子集加入psfor (it = ps1.begin(); it != ps1.end(); it++) {ps.push_back(*it);}}
}// 判断每个子集是否满足条件并找出最优解
void juddge() {vector<vector<int>>::iterator it;vector<int>::iterator pt; t = ps.end(); // 遍历所有子集for (it = ps.begin(); it != ps.end(); it++) {int sumv = 0; // 当前子集的总价值int sumw = 0; // 当前子集的总重量// 遍历当前子集中的物品编号for (pt = (*it).begin(); pt != (*it).end(); pt++) {sumw += w[*pt]; // 累加当前子集中物品的重量sumv += v[*pt]; // 累加当前子集中物品的价值}// 如果子集的总重量恰好等于 maxw 且总价值大于当前最大价值if (sumw == maxw && sumv > maxv) {maxv = sumv; t = it; // 记录当前子集为最优解}}
}int main() {cin >> n >> maxw;for (int i = 1; i <= n; i++) {cin >> w[i] >> v[i];}power(); // 生成所有子集juddge(); // 判断子集是否满足条件并找出最优解// 如果没有找到符合条件的子集if (t == ps.end()) {cout << "No" << endl; // 输出 Nocout << "0"; // 输出总价值为0}else {// 输出最优解中的物品编号for (r = (*t).begin(); r != (*t).end(); r++) {cout << *r << " ";}cout << endl;cout << maxv;}return 0;
}
相关文章:
PTA 7-2 0/1背包问题(回溯法) 作者 王东 单位 贵州师范学院
0/1背包问题。给定一载重量为W的背包及n个重量为wi、价值为vi的物体,1≤i≤n,要求重量和恰好为W具有最大的价值。 输入格式: 第一行输入背包载重量W及背包个数n,再依次输入n行,每行为背包重量wi和价值vi。 输出格式: 第一行输出装入背包内…...
Matlab环形柱状图
数据准备: 名称 数值 Aa 21 Bb 23 Cc 35 Dd 47 保存为Excel文件后: % Load data from Excel file filename data.xlsx; % Ensure the file is in the current folder or provide full path dataTable readtable(filena…...
【AI大模型】探索GPT模型的奥秘:引领自然语言处理的新纪元
目录 🍔 GPT介绍 🍔 GPT的架构 🍔 GPT训练过程 3.1 无监督的预训练语言模型 3.2 有监督的下游任务fine-tunning 🍔 小结 学习目标 了解什么是GPT.掌握GPT的架构.掌握GPT的预训练任务. 🍔 GPT介绍 GPT是OpenAI公…...
5.Python爬虫相关
爬虫 爬虫原理 爬虫,又称网络爬虫,是一种自动获取网页内容的程序。它模拟人类浏览网页的行为,发送HTTP请求,获取网页源代码,再通过解析、提取等技术手段,获取所需数据。 HTTP请求与响应过程 爬虫首先向…...
Windows系统上配置eNSP环境的详细步骤
华为eNSP(Enterprise Network Simulation Platform)是一款针对华为数通网络设备的网络仿真平台,用于辅助工程师进行网络技术学习、方案验证和故障排查等工作。以下是在Windows系统上配置eNSP环境的详细步骤: 1. 准备工作 下载安…...
Database.NET——一款轻量级多数据库客户端工具
文章目录 Database.NET简介下载使用使用场景总结 Database.NET简介 Database.NET 是一个功能强大且易于使用的数据库管理工具,适用于多种数据库系统。它为开发者和数据库管理员提供了一个统一的界面,可以方便地管理和操作不同类型的数据库。 支持的数据…...
新浪微博C++面试题及参考答案
多态是什么?请详细解释其实现原理,例如通过虚函数表实现。 多态是面向对象编程中的一个重要概念,它允许不同的对象对同一消息或函数调用做出不同的响应,使得程序具有更好的可扩展性和灵活性。 在 C 中,多态主要通过虚函…...
计算机视觉目标检测-1
文章目录 摘要Abstract1.目标检测任务描述1.1 目标检测分类算法1.2 目标定位的简单实现思路1.2.1 回归位置 2.R-CNN2.1 目标检测-Overfeat模型2.1.1 滑动窗口 2.2 目标检测-RCNN模型2.2.1 非极大抑制(NMS) 2.3 目标检测评价指标 3.SPPNet3.1 spatial pyr…...
【物联网技术与应用】实验15:电位器传感器实验
实验15 电位器传感器实验 【实验介绍】 电位器可以帮助控制Arduino板上的LED闪烁的时间间隔。 【实验组件】 ● Arduino Uno主板* 1 ● 电位器模块* 1 ● USB电缆*1 ● 面包板* 1 ● 9V方型电池* 1 ● 跳线若干 【实验原理】 模拟电位器是模拟电子元件,模…...
java常用类(上)
笔上得来终觉浅,绝知此事要躬行 🔥 个人主页:星云爱编程 🔥 所属专栏:javase 🌷追光的人,终会万丈光芒 🎉欢迎大家点赞👍评论📝收藏⭐文章 目录 一、包装类 1.1包装类…...
包管理工具npm、yarn、pnpm、cnpm详解
1. 包管理工具 1.1 npm # 安装 $ node 自带 npm# 基本用法 npm install package # 安装包 npm install # 安装所有依赖 npm install -g package # 全局安装 npm uninstall package # 卸载包 npm update package # 更新包 npm run script #…...
CI/CD是什么?
CI/CD 定义 CI/CD 代表持续集成和持续部署(或持续交付)。它是一套实践和工具,旨在通过自动化构建、测试和部署来改进软件开发流程,使您能够更快、更可靠地交付代码更改。 持续集成 (CI):在共享存储库中自动构建、测试…...
[Java]合理封装第三方工具包(附视频)
-1.视频链接 视频版: 视频版会对本文章内容进行详细解释 [Java]合理封装第三方工具包_哔哩哔哩_bilibili 0.核心思想 对第三方工具方法进行封装,使其本地化,降低记忆和使用成本 1.背景 在我们的项目中,通常会引用一些第三方工具包,或者是使用jdk自带的一些工具类 例如: c…...
常规配置、整合IDEA
目录 Redis常规配置 tcp-keepalive security Jedis RedisTemplate 连接池技术 Lua脚本 Jedis集群 Redis应用问题&解决方案 缓存穿透 缓存击穿 缓存雪崩 分布式锁 Redis实现分布式锁 Redis新功能 ACL Redis常规配置 tcp-keepalive security redis.conf中…...
用Python写炸金花游戏
文章目录 **代码分解与讲解**1. **扑克牌的生成与洗牌**2. **给玩家发牌**3. **打印玩家的手牌**4. **定义牌的优先级**5. **判断牌型**6. **确定牌型优先级**7. **比较两手牌的大小**8. **计算每个玩家的牌型并找出赢家**9. **打印结果** 完整代码 以下游戏规则: 那…...
计算机的错误计算(一百九十二)
摘要 用两个大模型计算 csc(0.999), 其中,0.999是以弧度为单位的角度,结果保留5位有效数字。两个大模型均给出了 Python代码与答案。但是,答案是错误的。 例1. 计算 csc(0.999), 其中,0.999是以弧度为单位的角度,结…...
37 Opencv SIFT 特征检测
文章目录 Ptr<SIFT> SIFT::create示例 Ptr SIFT::create Ptr<SIFT> SIFT::create(int nfeatures 0,int nOctaveLayers 3,double contrastThreshold 0.04,double edgeThreshold 10,double sigma 1.6 );参数说明:nfeatures:类型&#x…...
Nginx界的天花板-Oracle 中间件OHS 11g服务器环境搭建
环境信息 服务器基本信息 如下表,本次安装总共使用2台服务器,具体信息如下: 服务器IP DNS F5配置 OHS1 172.xx.xx.xx ohs01.xxxxxx.com ohs.xxxxxx.com OHS2 172.xx.xx.xx ohs02.xxxxxx.com 服务器用户角色信息均为:…...
域名解析协议
一、DNS简述 DNS协议是一种应用层协议,用于将域名转换为对应的IP地址,使得客户端可以通过域名来访问Internet上的各种资源 DNS的基础设施是由分层的DNS服务器实现的分布式数据库,它运行在UDP之上,通常使用端口号53 DN…...
微信小程序给外面的view设置display:flex;后为什么无法给里面的view设置宽度
如果父盒子view设置了display:flex,子view设置宽度值无效,宽度值都是随着内容多少而改变: 问题视图: 原因: flex布局元素的子元素,自动获得了flex-shrink的属性 解决方法: 给子view增加:fl…...
[特殊字符] 智能合约中的数据是如何在区块链中保持一致的?
🧠 智能合约中的数据是如何在区块链中保持一致的? 为什么所有区块链节点都能得出相同结果?合约调用这么复杂,状态真能保持一致吗?本篇带你从底层视角理解“状态一致性”的真相。 一、智能合约的数据存储在哪里…...
高危文件识别的常用算法:原理、应用与企业场景
高危文件识别的常用算法:原理、应用与企业场景 高危文件识别旨在检测可能导致安全威胁的文件,如包含恶意代码、敏感数据或欺诈内容的文档,在企业协同办公环境中(如Teams、Google Workspace)尤为重要。结合大模型技术&…...
解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错
出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上,所以报错,到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本,cu、torch、cp 的版本一定要对…...
多种风格导航菜单 HTML 实现(附源码)
下面我将为您展示 6 种不同风格的导航菜单实现,每种都包含完整 HTML、CSS 和 JavaScript 代码。 1. 简约水平导航栏 <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><meta name"viewport&qu…...
华为OD机考-机房布局
import java.util.*;public class DemoTest5 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseSystem.out.println(solve(in.nextLine()));}}priv…...
Ubuntu Cursor升级成v1.0
0. 当前版本低 使用当前 Cursor v0.50时 GitHub Copilot Chat 打不开,快捷键也不好用,当看到 Cursor 升级后,还是蛮高兴的 1. 下载 Cursor 下载地址:https://www.cursor.com/cn/downloads 点击下载 Linux (x64) ,…...
永磁同步电机无速度算法--基于卡尔曼滤波器的滑模观测器
一、原理介绍 传统滑模观测器采用如下结构: 传统SMO中LPF会带来相位延迟和幅值衰减,并且需要额外的相位补偿。 采用扩展卡尔曼滤波器代替常用低通滤波器(LPF),可以去除高次谐波,并且不用相位补偿就可以获得一个误差较小的转子位…...
沙箱虚拟化技术虚拟机容器之间的关系详解
问题 沙箱、虚拟化、容器三者分开一一介绍的话我知道他们各自都是什么东西,但是如果把三者放在一起,它们之间到底什么关系?又有什么联系呢?我不是很明白!!! 就比如说: 沙箱&#…...
在 Visual Studio Code 中使用驭码 CodeRider 提升开发效率:以冒泡排序为例
目录 前言1 插件安装与配置1.1 安装驭码 CodeRider1.2 初始配置建议 2 示例代码:冒泡排序3 驭码 CodeRider 功能详解3.1 功能概览3.2 代码解释功能3.3 自动注释生成3.4 逻辑修改功能3.5 单元测试自动生成3.6 代码优化建议 4 驭码的实际应用建议5 常见问题与解决建议…...
6.9-QT模拟计算器
源码: 头文件: widget.h #ifndef WIDGET_H #define WIDGET_H#include <QWidget> #include <QMouseEvent>QT_BEGIN_NAMESPACE namespace Ui { class Widget; } QT_END_NAMESPACEclass Widget : public QWidget {Q_OBJECTpublic:Widget(QWidget *parent nullptr);…...
