当前位置: 首页 > 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;…...

浏览器访问 AWS ECS 上部署的 Docker 容器(监听 80 端口)

✅ 一、ECS 服务配置 Dockerfile 确保监听 80 端口 EXPOSE 80 CMD ["nginx", "-g", "daemon off;"]或 EXPOSE 80 CMD ["python3", "-m", "http.server", "80"]任务定义&#xff08;Task Definition&…...

龙虎榜——20250610

上证指数放量收阴线&#xff0c;个股多数下跌&#xff0c;盘中受消息影响大幅波动。 深证指数放量收阴线形成顶分型&#xff0c;指数短线有调整的需求&#xff0c;大概需要一两天。 2025年6月10日龙虎榜行业方向分析 1. 金融科技 代表标的&#xff1a;御银股份、雄帝科技 驱动…...

Lombok 的 @Data 注解失效,未生成 getter/setter 方法引发的HTTP 406 错误

HTTP 状态码 406 (Not Acceptable) 和 500 (Internal Server Error) 是两类完全不同的错误&#xff0c;它们的含义、原因和解决方法都有显著区别。以下是详细对比&#xff1a; 1. HTTP 406 (Not Acceptable) 含义&#xff1a; 客户端请求的内容类型与服务器支持的内容类型不匹…...

Qt Widget类解析与代码注释

#include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this); }Widget::~Widget() {delete ui; }//解释这串代码&#xff0c;写上注释 当然可以&#xff01;这段代码是 Qt …...

为什么需要建设工程项目管理?工程项目管理有哪些亮点功能?

在建筑行业&#xff0c;项目管理的重要性不言而喻。随着工程规模的扩大、技术复杂度的提升&#xff0c;传统的管理模式已经难以满足现代工程的需求。过去&#xff0c;许多企业依赖手工记录、口头沟通和分散的信息管理&#xff0c;导致效率低下、成本失控、风险频发。例如&#…...

学校招生小程序源码介绍

基于ThinkPHPFastAdminUniApp开发的学校招生小程序源码&#xff0c;专为学校招生场景量身打造&#xff0c;功能实用且操作便捷。 从技术架构来看&#xff0c;ThinkPHP提供稳定可靠的后台服务&#xff0c;FastAdmin加速开发流程&#xff0c;UniApp则保障小程序在多端有良好的兼…...

智能在线客服平台:数字化时代企业连接用户的 AI 中枢

随着互联网技术的飞速发展&#xff0c;消费者期望能够随时随地与企业进行交流。在线客服平台作为连接企业与客户的重要桥梁&#xff0c;不仅优化了客户体验&#xff0c;还提升了企业的服务效率和市场竞争力。本文将探讨在线客服平台的重要性、技术进展、实际应用&#xff0c;并…...

【RockeMQ】第2节|RocketMQ快速实战以及核⼼概念详解(二)

升级Dledger高可用集群 一、主从架构的不足与Dledger的定位 主从架构缺陷 数据备份依赖Slave节点&#xff0c;但无自动故障转移能力&#xff0c;Master宕机后需人工切换&#xff0c;期间消息可能无法读取。Slave仅存储数据&#xff0c;无法主动升级为Master响应请求&#xff…...

Springboot社区养老保险系统小程序

一、前言 随着我国经济迅速发展&#xff0c;人们对手机的需求越来越大&#xff0c;各种手机软件也都在被广泛应用&#xff0c;但是对于手机进行数据信息管理&#xff0c;对于手机的各种软件也是备受用户的喜爱&#xff0c;社区养老保险系统小程序被用户普遍使用&#xff0c;为方…...

CRMEB 中 PHP 短信扩展开发:涵盖一号通、阿里云、腾讯云、创蓝

目前已有一号通短信、阿里云短信、腾讯云短信扩展 扩展入口文件 文件目录 crmeb\services\sms\Sms.php 默认驱动类型为&#xff1a;一号通 namespace crmeb\services\sms;use crmeb\basic\BaseManager; use crmeb\services\AccessTokenServeService; use crmeb\services\sms\…...