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

背包 问题

1、背包问题

1.1、01背包

题目:

有n件物品和一个容量为m的背包,第i件物品的体积是v[ i ],价值是w[ i ],每件物品只有一件,求在不超过背包容量的前提下,可以放的物品的最大价值是多少

基本思路:

每个物品只有一件,考虑去或者不取

状态设计:

//二维
状态表示:f[i][j]集合:从前i个物品中选,总体积不超过j的物品的价值属性:max
状态计算:选第i个物品:f[i][j]=min(f[i-1][j-v[i]]+w[i],f[i][j]);不选第i个物品:f[i][j]=min(f[i-1][j],f[i][j]);//时间复杂度基本无法优化,空间复杂度可以优化
//一维:由于每一次状态计算时仅需考虑计算上一个物品后的状态,但需要从m~0枚举体积
状态计算:f[j]=max(f[j],f[j-v[i]]+w[i]);

代码:

//不优化:二维
#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;
const int N=1100;
int f[N][N];
int w[N],v[N];
int n,m;
int res;int main()
{cin>>n>>m;for(int i=1;i<=n;i++)   cin>>v[i]>>w[i];for(int i=1;i<=n;i++){for(int j=0;j<=m;j++){f[i][j]=f[i-1][j];if(j>=v[i])f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);}}for(int i=1;i<=m;i++)   res=max(f[n][i],res);cout<<res;return 0;
}
//优化·一维
#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;
const int N = 1111;
int f[N];
int n,m;
int v[N],w[N];
int main()
{cin>>n>>m;for(int i=1;i<=n;i++)   cin>>v[i]>>w[i];for(int i=1;i<=n;i++){for(int j=m;j>=v[i];j--){f[j]=max(f[j],f[j-v[i]]+w[i]);}}cout<<f[m];return 0;
}

1.2、完全背包

题目:

有n件物品和一个容量为m的背包,第i件物品的体积是v[ i ],价值是w[ i ],每件物品有无限多件,求在不超过背包容量的前提下,可以放的物品的最大价值是多少

基本思路:

由于每种物品有无限多件,所以对于每种物品有无限多种选择(选0个,选1个······选n个)

状态设计:

状态表示:f[i][j]集合:从前i个物品中选,总体积不超过j的物品的价值属性:max
状态计算://朴素O(n^3):枚举每件物品取多少件(k:0~j/v[i])f[i][j]=max(f[i][j],f[i-k][j-k*v[i]]+k*w[i])//优化:朴素版本时:f[i][j] =max{f[i-1][j], f[i-1][j-v[i]]+w[i], f[i-2][j-2*v[i]]+2*w[i]. ······ }f[i][j-v[i]] =max{           f[i-1][j-v[i]],      f[i-2][j-2*v[i]]+w[i]. ······ }由以上两个式子可知:不选第i个:f[i][j]=f[i-1][j]选第i个(不确定个数):f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i]);//优化为一维f[j]=max(f[j],f[j-v[i]]+w[i])

代码:

//朴素做法  会超时
#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;int n,m;
const int N = 1111;
int v[N],w[N];
int f[N][N];int main()
{cin>>n>>m;for(int i=1;i<=n;i++)   cin>>v[i]>>w[i];for(int i=1;i<=n;i++){for(int j=0;j<=m;j++){for(int k=0;k*v[i]<=j;k++){f[i][j]=max(f[i-1][j-k*v[i]]+k*w[i],f[i][j]);}}}cout<<f[n][m];return 0;
}优化版本(二维)
#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;int n,m;
const int N = 1111;
int v[N],w[N];
int f[N][N];int main()
{cin>>n>>m;for(int i=1;i<=n;i++)   cin>>v[i]>>w[i];for(int i=1;i<=n;i++){for(int j=0;j<=m;j++){f[i][j]=f[i-1][j];if(j>=v[i]){f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i]);}}}cout<<f[n][m];return 0;
}//再优化版本(一维)
#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;int n,m;
const int N = 1111;
int v[N],w[N];
int f[N];int main()
{cin>>n>>m;for(int i=1;i<=n;i++)   cin>>v[i]>>w[i];for(int i=1;i<=n;i++){for(int j=v[i];j<=m;j++){f[j]=max(f[j],f[j-v[i]]+w[i]);}}cout<<f[m];return 0;
}

1.3、多重背包

题目:

有n种物品和一个容量为m的背包,第 i 种物品有s[ i ]件,每件体积是v[ i ],价值是w[ i ],求在不超过背包容量的前提下,可以放的物品的最大价值是多少

基本思路(二进制优化版本):

任何一个数可以用二进制来表示,也就是20、21、……、2n 其中一项或几项的和

对于每一种物品划分为k组,每组的数量为2的倍数

然后转换为01背包进行考虑
状态设计:

同01背包

代码

#include<iostream>
#include<cstring>
#include<algorithm>using namespace std;
const int N=25000;
int n,m;
int w[N],v[N];
int f[N];int main()
{cin>>n>>m;int cnt=0;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){int a,b,s;cin>>a>>b>>s;int k=1;while(s>=k){cnt++;v[cnt]=a*k;w[cnt]=b*k;s-=k;k*=2;}if(s){cnt++;v[cnt]=a*s;w[cnt]=b*s;}}}n=cnt;for(int i=1;i<=n;i++){for(int j=m;j>=v[i];j--){f[j]=max(f[j],f[j-v[i]]+w[i]);}}cout<<f[m];
}

1.4、分组背包

题目:

有n件物品(可以被分成几组)和一个容量为m的背包,第i件物品的体积是v[ i ],价值是w[ i ],组号为p[ i ],每组只能选一个物品,求在不超过背包容量的前提下,可以放的物品的最大价值是多少

基本思路:

对于每组物品考虑取(取哪一件)或者不取

状态设计:

状态表示:f[i][j]集合:从前i组中选,总体积不超过j的物品的价值属性:max
状态计算:第i组不选:f[i][j]=f[i-1][j]选第i组的第k个:f[i][j]=max(f[i-1][j-v[i][k]]+w[i][k])//优化为一维f[j]=max(f[j],f[j-v[i][k]]+w[i][k])

代码:

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;
int n,m;
int w[110][110],v[110][110];
int s[110];
//二维  int f[110][110];
int f[110];
int main()
{cin>>n>>m;for(int i=1;i<=n;i++){cin>>s[i];for(int j=1;j<=s[i];j++)  scanf("%d%d",&v[i][j],&w[i][j]);}/*二维for(int i=1;i<=n;i++){for(int j=0;j<=m;j++){f[i][j]=f[i-1][j];for(int k=0;k<=s[i];k++){if(j-v[i][k]>=0){f[i][j]=max(f[i][j],f[i-1][j-v[i][k]]+w[i][k]);}}}}cout<<f[n][m];*/for(int i=1;i<=n;i++){for(int j=m;j>=0;j--){f[j]=f[j];for(int k=0;k<=s[i];k++){if(j-v[i][k]>=0){f[j]=max(f[j],f[j-v[i][k]]+w[i][k]);}}}}cout<<f[m];return 0;
}

1.5、混合背包

题目:

1.1、1.2、1.3三种背包混合起来,即有的物品只可以取一次(01背包),有的物品可以取无限次(完全背包),有的物品可以取的次数有一个上限(多重背包)。

基本思路:

同上,分情况考虑各物品

状态设计:

同上

例题+代码:

有N种物品和一个容量是 V的背包。
物品一共有三类:
第一类物品只能用1次(01背包);
第二类物品可以用无限次(完全背包);
第三类物品最多只能用 si 次(多重背包);
每种体积是 vi,价值是 wi。
求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。
输出最大价值。
#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N=1010;int n,m;
int v[N],w[N],s[N];
int f[N];int main()
{cin>>n>>m;for(int i=1;i<=n;i++){scanf("%d%d%d",&v[i],&w[i],&s[i]);if(s[i]==-1)    s[i]=1;}for(int i=1;i<=n;i++){if(s[i]==0){for(int j=v[i];j<=m;j++){f[j]=max(f[j],f[j-v[i]]+w[i]);}}else{for(int k=1;k<=s[i];k*=2){for(int j=m;j>=k*v[i];j--){f[j]=max(f[j],f[j-k*v[i]]+k*w[i]);}s[i]-=k;}if(s[i]){for(int j=m;j>=s[i]*v[i];j--){f[j]=max(f[j],f[j-s[i]*v[i]]+s[i]*w[i]);}}}}cout<<f[m];
}

1.6、二维费用的背包

题目:

对于每种物品有两个限制条件,即除了对体积有限制外,还有一个限制量

基本思路:

增加了一重限制,所以需要增加一维变量

状态设计:

状态表示:f[i][j][k]集合:从前i个中选,体积不超过j,重量不超过k的价值区间:max
状态计算:同上

代码:

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;
const int N=1010;int n,M,W;
int v[N],m[N],w[N];
int f[110][110];int main()
{cin>>n>>M>>W;for(int i=1;i<=n;i++)   scanf("%d%d%d",&v[i],&m[i],&w[i]);for(int i=1;i<=n;i++){for(int j=M;j>=v[i];j--){for(int k=W;k>=m[i];k--){f[j][k]=max(f[j][k],f[j-v[i]][k-m[i]]+w[i]);}}}cout<<f[M][W];return 0;
}

相关文章:

背包 问题

1、背包问题 1.1、01背包 题目&#xff1a; 有n件物品和一个容量为m的背包&#xff0c;第i件物品的体积是v[ i ]&#xff0c;价值是w[ i ]&#xff0c;每件物品只有一件&#xff0c;求在不超过背包容量的前提下&#xff0c;可以放的物品的最大价值是多少 基本思路&#xff…...

蓝牙资讯|安卓将加强耳机音量监控,耳机查找功能将更加普遍

为了保护用户的听力健康&#xff0c;Android 14 将增加一项新功能&#xff0c;当用户使用耳机听音乐时&#xff0c;如果音量过高或持续时间过长&#xff0c;系统会发出警告&#xff0c;并自动降低音量。这个功能叫做“耳机音量过高警告&#xff08;headphone loud sound alert&…...

vue,element。监听快捷键粘贴图片,添加到el-upload的列表。

在①中&#xff0c;粘贴图片&#xff0c;图片能够自动添加到底下el-upload组件的文件列表②。 // 对应① <el-card><el-tooltip content"粘贴图片至此" placement"top"><input readonly class"pasteImg" paste.prevent"hand…...

时序预测 | MATLAB实现基于CNN-BiLSTM卷积双向长短期记忆神经网络的时间序列预测-递归预测未来(多指标评价)

时序预测 | MATLAB实现基于CNN-BiLSTM卷积双向长短期记忆神经网络的时间序列预测-递归预测未来(多指标评价) 目录 时序预测 | MATLAB实现基于CNN-BiLSTM卷积双向长短期记忆神经网络的时间序列预测-递归预测未来(多指标评价)预测结果基本介绍程序设计参考资料 预测结果 基本介绍…...

编织梦想:SpringBoot AOP 教程与自定义日志切面完整实战

什么是 AOP AOP 是指通过预编译方式和运行期动态代理的方式&#xff0c;在不修改源代码的情况下对程序进行功能增强的一种技术。AOP 不是面向对象编程&#xff08;OOP&#xff09;的替代品&#xff0c;而是 OOP 的补充和扩展。它是一个新的维度&#xff0c;用来表达横切问题&a…...

AssignableTypeFilter 和 AnnotationTypeFilter什么区别?

在 Spring 框架中&#xff0c;AssignableTypeFilter 和 AnnotationTypeFilter 都是用于在组件扫描过程中进行过滤的工具类&#xff0c;用于筛选出特定类型或特定注解的类。它们的主要区别在于筛选的侧重点和使用方式。 AssignableTypeFilter&#xff1a; AssignableTypeFilte…...

TCP-事件模型

#include "main.h"VOID Server_write_error() {}/*1.打开网络库 * 2.校验网络库版本 * 3.创建SOCKET * 4.绑定IP地址和端口 * 5.开始监听 * 6.创建客户端socket/接受链接 * 7.与客户端收发消息 * 8.(6.7)两步的函数accept&#xff0c;send,recv 有堵塞&#xff0c;可…...

typescript 声明文件

作用 1、为已存在js库提供类型信息&#xff0c;这样在ts项目中使用这些库时候&#xff0c;就像用ts一样&#xff0c;会有代码提示、类型保护等机制 2、项目内共享类型&#xff1a;如果多个.ts文件中都用到同一个类型&#xff0c;此时可以创建.d.ts文件提供该类型&#xff0c;…...

BC96 有序序列判断

描述 输入一个整数序列&#xff0c;判断是否是有序序列&#xff0c;有序&#xff0c;指序列中的整数从小到大排序或者从大到小排序(相同元素也视为有序)。 数据范围&#xff1a;3≤n≤50 序列中的值都满足1≤val≤100。 输入描述 第一行输入一个整数N(3≤N≤50)。 第二行…...

QT操作excel的两种方式 QT基础入门【Excel的操作】

QT操作excel的方式有两种&#xff1a;QAxObject 和QtXlsx QAxObject是通过调用office或者wps组件来实现对excel图表的操作的。只有装office软件或者wps软件就可以实现&#xff0c;但是 如果只装了office软件&#xff0c;有时可以用有时不可以用&#xff1b;如果只装wps软件&a…...

c++ qt--QString,弹出框(第二部分)

c qt–QString&#xff0c;弹出框&#xff08;第二部分&#xff09; 一.QString 1.所用头文件 #include<QString>2.功能 1.初始化 可以用字符&#xff0c;常量字符串、字符指针、字符数组等类型给QString进行初始化 QString str2"4567";//进行初始化2.拼…...

CSS自学框架之动画

这一节&#xff0c;自学CSS动画。主要学习了淡入淡出、淡入缩放、缩放、移动、旋转动画效果。先看一下成果。 优雅的过渡动画&#xff0c;为你的页面添加另一份趣味&#xff01; 在你的选择器里插入 animation 属性&#xff0c;并添加框架内置的 keyframes 即可实现&#xff0…...

RabbitMQ的5种消息队列

RabbitMQ的5种消息队列 1、七种模式介绍与应用场景 1.1 简单模式(Hello World) 一个生产者对应一个消费者&#xff0c;RabbitMQ 相当于一个消息代理&#xff0c;负责将 A 的消息转发给 B。 应用场景&#xff1a;将发送的电子邮件放到消息队列&#xff0c;然后邮件服务在队列…...

【C语言】选择排序

基本原理 先找到数组中最大的那个数&#xff0c;将最大的数放到数组最右端&#xff08;交换a[maxid]和a[len-1]这两个数的位置&#xff09;&#xff0c;然后继续从a[0]到a[len-2]中找到最大的数&#xff0c;然后交换a[maxid]和a[len-2]位置&#xff0c;依次查找交换&#xff0c…...

异步更新队列 - Vue2 响应式

前言 这篇文章分析了 Vue 更新过程中使用的异步更新队列的相关代码。通过对异步更新队列的研究和学习&#xff0c;加深对 Vue 更新机制的理解 什么是异步更新队列 先看看下面的例子&#xff1a; <div id"app"><div id"div" v-if"isShow&…...

【Unity的URP渲染管线下实现扩展后处理Volume组件_TemporalAntiAliasing(TAA)_抗锯齿(附带下载链接)】

【Unity的URP渲染管线下的TAA抗锯齿】 背景:1. Unity内置的抗锯齿只能够满足部分画面需求。展示一个锯齿示例。2. 在75寸大屏电视上跑通展示一个锯齿示例。- 在Camera上配置3. 安装了一个TAA组建,最后打包APK在安卓机上运行报错。- 经过测试排查,发现是没有将后处理的shader…...

NineData通过AWS FTR认证,打造安全可靠的数据管理平台

近日&#xff0c;NineData 作为新一代的云原生智能数据管理平台&#xff0c;成功通过了 AWS&#xff08;Amazon Web Service&#xff09;的 FTR 认证。NineData 在 FTR 认证过程中表现出色&#xff0c;成功通过了各项严格的测试和评估&#xff0c;在数据安全管理、技术应用、流…...

Qt应用开发(基础篇)——滚屏区域类 QScrollArea

一、前言 QScrollArea类继承于QAbstractScrollArea&#xff0c;QAbstractScrollArea继承于QFrame&#xff0c;是Qt滚动视图的常用部件。 滚屏区域基类 QAbstractScrollArea 框架类 QFrame QScrollArea类提供了对另一个小部件的滚动视图&#xff0c;基础功能、滚动条控制、界面策…...

安装最新版chromedriver 116,亲测可用

Version Selection...

html题库

什么是HTML? HTML的全称为 超文本标记语言 &#xff0c;是一种 标记语言 。 它包括一系列标签 &#xff0c;通过这些标签可以将网络上的文档格式统一&#xff0c;使分散的 Internet 资源连接为一个逻辑整体。 DOCTYPE 的作用是什么&#xff1f;标准模式与兼容模式&#xff08;…...

接口测试中缓存处理策略

在接口测试中&#xff0c;缓存处理策略是一个关键环节&#xff0c;直接影响测试结果的准确性和可靠性。合理的缓存处理策略能够确保测试环境的一致性&#xff0c;避免因缓存数据导致的测试偏差。以下是接口测试中常见的缓存处理策略及其详细说明&#xff1a; 一、缓存处理的核…...

CTF show Web 红包题第六弹

提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框&#xff0c;很难让人不联想到SQL注入&#xff0c;但提示都说了不是SQL注入&#xff0c;所以就不往这方面想了 ​ 先查看一下网页源码&#xff0c;发现一段JavaScript代码&#xff0c;有一个关键类ctfs…...

模型参数、模型存储精度、参数与显存

模型参数量衡量单位 M&#xff1a;百万&#xff08;Million&#xff09; B&#xff1a;十亿&#xff08;Billion&#xff09; 1 B 1000 M 1B 1000M 1B1000M 参数存储精度 模型参数是固定的&#xff0c;但是一个参数所表示多少字节不一定&#xff0c;需要看这个参数以什么…...

DockerHub与私有镜像仓库在容器化中的应用与管理

哈喽&#xff0c;大家好&#xff0c;我是左手python&#xff01; Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库&#xff0c;用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...

在HarmonyOS ArkTS ArkUI-X 5.0及以上版本中,手势开发全攻略:

在 HarmonyOS 应用开发中&#xff0c;手势交互是连接用户与设备的核心纽带。ArkTS 框架提供了丰富的手势处理能力&#xff0c;既支持点击、长按、拖拽等基础单一手势的精细控制&#xff0c;也能通过多种绑定策略解决父子组件的手势竞争问题。本文将结合官方开发文档&#xff0c…...

安宝特方案丨XRSOP人员作业标准化管理平台:AR智慧点检验收套件

在选煤厂、化工厂、钢铁厂等过程生产型企业&#xff0c;其生产设备的运行效率和非计划停机对工业制造效益有较大影响。 随着企业自动化和智能化建设的推进&#xff0c;需提前预防假检、错检、漏检&#xff0c;推动智慧生产运维系统数据的流动和现场赋能应用。同时&#xff0c;…...

Golang dig框架与GraphQL的完美结合

将 Go 的 Dig 依赖注入框架与 GraphQL 结合使用&#xff0c;可以显著提升应用程序的可维护性、可测试性以及灵活性。 Dig 是一个强大的依赖注入容器&#xff0c;能够帮助开发者更好地管理复杂的依赖关系&#xff0c;而 GraphQL 则是一种用于 API 的查询语言&#xff0c;能够提…...

论文浅尝 | 基于判别指令微调生成式大语言模型的知识图谱补全方法(ISWC2024)

笔记整理&#xff1a;刘治强&#xff0c;浙江大学硕士生&#xff0c;研究方向为知识图谱表示学习&#xff0c;大语言模型 论文链接&#xff1a;http://arxiv.org/abs/2407.16127 发表会议&#xff1a;ISWC 2024 1. 动机 传统的知识图谱补全&#xff08;KGC&#xff09;模型通过…...

Python 包管理器 uv 介绍

Python 包管理器 uv 全面介绍 uv 是由 Astral&#xff08;热门工具 Ruff 的开发者&#xff09;推出的下一代高性能 Python 包管理器和构建工具&#xff0c;用 Rust 编写。它旨在解决传统工具&#xff08;如 pip、virtualenv、pip-tools&#xff09;的性能瓶颈&#xff0c;同时…...

云原生安全实战:API网关Kong的鉴权与限流详解

&#x1f525;「炎码工坊」技术弹药已装填&#xff01; 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、基础概念 1. API网关&#xff08;API Gateway&#xff09; API网关是微服务架构中的核心组件&#xff0c;负责统一管理所有API的流量入口。它像一座…...