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

【算法刨析】完全背包

完全背包与01背包的区别

01背包对于一个物品只能选择一次,但是完全背包可以选择任意次; 

思路

和01背包类似,01背包我们只需要判断选或不选,完全背包也是如此,不同的是,对于这个物品我们在判断选后在增加一次选择的机会,直到不选,跳转至下一个物品即可;

一般代码:

 f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);

第k次,不选的话就是它本身,选的话就是直接选择k次即可;

当然这个代码在数据稍微大一点的时候就会超出时间限制;

#include<iostream>
using namespace std;
const int N=1004;
int f[N][N];
int w[N],v[N];int main()
{int n,m;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][j],f[i-1][j-k*v[i]]+k*w[i]);}}}cout<<f[n][m]<<endl;
}

优化思路

上面代码会超出时间限制是因为三层循环,下面我们来把第三层循环优化掉:

f[i][j]=max(f[i][j],f[i-1][j-v]+w,f[i-1][j-2*v]+2*w,f[i-1][j-3*v]+3*w......f[i-1][j-k*v]+k*w)

f[i][j-v]=max(             f[i][j-v],f[i-1][j-2*v]+w,f[i-1][j-3*v]+2*w......f[i-1][j-k*v]+k*w)

f[i-1][j-v]+w,f[i-1][j-2*v]+2*w,f[i-1][j-3*v]+3*w......f[i-1][j-k*v]+k*w 不就是f[i][j-v]+w

那么我们可以得到:f[i][j]=max(f[i][j],f[i-1][j-v]+w)

这样我们不就可以不用写第三层循环了吗?

直接用:

            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]);

优化代码:

#include<iostream>
using namespace std;
const int N=1004;
int f[N][N];
int w[N],v[N];int main()
{int n,m;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]<<endl;
}

我们来看一下核心代码:

            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]);

还记得01背包的代码吗?
             f[i][j] = f[i - 1][j];

             if(j>=v[i])
             f[i][j]= max( f[i - 1][j],f[i - 1][j - v[i]] + w[i] );

是不是只有(红色标记):

  f[i][j]= max( f[i - 1][j],f[i - 1][j - v[i]] + w[i] );不同

再次优化代码:

注意:

这里我的j的大小是从小到大开始的:

01背包中,f[i][j]= max( f[i - 1][j],f[i - 1][j - v[i]] + w[i] );对于f[j]就相当于f[i-1][j]的大小,如果从小到大遍历,那么f[i-1][j]的大小就会发现变化,那么优化后的代码就不满足我们所推导的公式,所以我们要从大到小;

类比于01背包,完全背包的公式, f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i]);对于这个公式如果从大到小就会改变f[i][j]的大小,不满足所推导的公式;

#include<iostream>
#include<cstring>
using namespace std;
const int N=1e4;
int f[N];
int w[N],v[N];int main()
{int n,m;cin>>n>>m;for(int i=0;i<n;i++)cin>>v[i]>>w[i];for(int i=0;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]<<endl;
}

以上就是全部内容!!

相关文章:

【算法刨析】完全背包

完全背包与01背包的区别 01背包对于一个物品只能选择一次&#xff0c;但是完全背包可以选择任意次&#xff1b; 思路 和01背包类似&#xff0c;01背包我们只需要判断选或不选&#xff0c;完全背包也是如此&#xff0c;不同的是&#xff0c;对于这个物品我们在判断选后在增加一…...

notepad++

文章目录 换行 换行 根据需要选择是否要自动换行或者一行展示。 点击视图 选中或者取消选中自动换行...

Python ValueError: bad transparency mask

修改前 修复后 运行正常 from PIL import Image# 读取图片 #报错信息解决ValueError: bad transparency mask--相关文档地址https://blog.csdn.net/kalath_aiur/article/details/103945309 #1. 检查 alpha 通道是否是一个有效的掩码。如果不是&#xff0c;则需要对 alpha 通道…...

Linux本地部署Nightingale夜莺监控并实现远程访问提高运维效率

&#x1f49d;&#x1f49d;&#x1f49d;欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学…...

开关电源功率测试方法:输入、输出功率测试步骤

在现代电子设备中&#xff0c;开关电源扮演着至关重要的角色&#xff0c;其效率和稳定性直接影响到整个系统的性能。因此&#xff0c;对开关电源进行功率测试成为了电源管理的重要环节。本文将详细介绍如何使用DC-DC电源模块测试系统对开关电源的输入输出功率进行准确测量&…...

QT 文字转语言插件

1.在工程.pro文件中添加 QT texttospeech 2.在头文件中添加 #include <QTextToSpeech> 3.使用的方法 QString str"欢迎使用智慧教育学习平台";QTextToSpeech *Speechernew QTextToSpeech;const QVector<QVoice> voices Speecher->availableV…...

Kubernetes(k8s)的认证(Authentication)策略解析

Kubernetes&#xff08;k8s&#xff09;的认证&#xff08;Authentication&#xff09;策略是确保只有经过验证的实体&#xff08;用户、服务账户等&#xff09;能够访问API服务器的基础安全措施。Kubernetes支持多种认证方法&#xff0c;以下是主要的认证策略&#xff1a; X50…...

Scikit-Learn决策树

Scikit-Learn决策树 1、决策树分类2、Scikit-Learn决策树分类2.1、Scikit-Learn决策树API2.2、Scikit-Learn决策树初体验2.3、Scikit-Learn决策树实践&#xff08;葡萄酒分类&#xff09; 1、决策树分类 2、Scikit-Learn决策树分类 2.1、Scikit-Learn决策树API 官方文档&#…...

Python面试题【python基础部分1-50】

Python面试题【python基础部分1-50】 Python面试题【python基础部分1-50】 Python面试题【python基础部分1-50】 问题&#xff1a;如何在Python中交换两个变量的值&#xff1f; 答案&#xff1a; a, b b, a问题&#xff1a;Python中的列表和元组有什么区别&#xff1f; 答案&…...

鸿蒙内核源码分析(Shell编辑篇) | 两个任务,三个阶段

系列篇从内核视角用一句话概括shell的底层实现为&#xff1a;两个任务&#xff0c;三个阶段。其本质是独立进程&#xff0c;因而划到进程管理模块。每次创建shell进程都会再创建两个任务。 客户端任务(ShellEntry)&#xff1a; 负责接受来自终端(控制台)敲入的一个个字符&…...

第Ⅷ章-Ⅱ 组合式API使用

第Ⅷ章-Ⅱ 组合式API使用 provide与inject的使用vue 生命周期的用法编程式路由的使用vuex的使用获取DOM的使用setup语法糖setup语法糖的基本结构响应数据的使用其它语法的使用引入组件的使用 父组件传值的使用defineProps 父传子defineEmits 子传父 provide与inject的使用 pro…...

stable-diffusion-webui配置

源码地址 https://github.com/AUTOMATIC1111/stable-diffusion-webui.git报错Fresh install fail to load AttributeError: NoneType object has no attribute _id pydantic降级 pip uninstall pydantic pip install pydantic1.10.11记得要把clip-vit-large-patch14放在opena…...

1+X电子商务数据采集渠道及工具选择(二)||电商数据采集API接口

电商数据采集API 接口 ◆适用范围 淘宝&#xff1a;可以采集到所属淘宝、天猫店铺的流量、销售、产品、运营相关数据;需要采集行业市场数据,则需要选择市场行情版。 京东&#xff1a;采集京东等其他平台店铺数据 jd.item_get 公共参数 名称类型必须描述keyString是调用key&…...

apinto OpenAPI

OpenApi 上游 查询列表 查询详情 新增 { "name": "jg_upstream", "driver": "http", "description": "通过postman添加上游", "scheme": "HTTPS", "retry":"1", "…...

XYCTF - web

目录 warm up ezMake ezhttp ezmd5 牢牢记住&#xff0c;逝者为大 ezPOP 我是一个复读机 ezSerialize 第一关 第二关 第三关 第一种方法&#xff1a; 第二种方法&#xff1a; ez?Make 方法一&#xff1a;利用反弹shell 方法二&#xff1a;通过进制编码绕过 ε…...

学习方法的重要性

原贴&#xff1a;https://www.cnblogs.com/feily/p/13999204.html 原贴&#xff1a;https://36kr.com/p/1236733055209095 1、 “一万小时定律”的正确和误区 正确&#xff1a; 天才和大师的非凡&#xff0c;不是真的天资超人一等&#xff0c;而是付出了持续不断的努力&…...

把现有的 Jenkins 容器推送到一个新的镜像标签,并且重新启动新的容器

要把现有的 Jenkins 容器推送到一个新的镜像标签&#xff0c;并且重新启动新的容器&#xff0c;你可以按照以下步骤操作&#xff1a; 停止当前正在运行的 Jenkins 容器&#xff08;如果你不想在操作时中断服务&#xff0c;可以跳过此步骤&#xff0c;直接进行下一步&#xff09…...

难以重现的 Bug如何处理

对很多测试人员&#xff08;尤其是对新手来说&#xff09;在工作过程中最不愿遇到的一件事情就是&#xff1a;在测试过 程中发现了一个问题&#xff0c;觉得是 bug&#xff0c;再试的时候又正常了。 碰到这样的事情&#xff0c;职业素养和测试人员长期养成的死磕的习性会让她…...

我与足球的故事 | 10年的热爱 | 伤病 | 悔恨 | 放弃 or 继续 | 小学生的碎碎念罢了

今天不分享技术博客&#xff0c;今天不知道为什么就是想写我和足球的故事&#xff08;手术完两个礼拜&#xff0c;手还是很疼那个&#xff0c;就连打字都费劲&#xff09;&#xff0c;上面两张图是我最喜欢的两个球星&#xff0c;当然因为之前特别喜欢巴萨&#xff0c;也特别喜…...

js图片回显的方法

直接上代码&#xff1a; <!DOCTYPE html> <html><head><meta charset"utf-8"><title></title></head><body>// HTML部分<input type"file" id"fileInput"><button onclick"show…...

Vue3实战:5分钟搞定全局WebSocket封装(含心跳检测与断线重连)

Vue3全局WebSocket封装实战&#xff1a;心跳检测与断线重连的最佳实践 WebSocket在现代Web应用中扮演着越来越重要的角色&#xff0c;特别是在需要实时数据更新的场景中。Vue3作为当前最流行的前端框架之一&#xff0c;与WebSocket的结合能够为开发者提供强大的实时交互能力。本…...

Google Test进阶玩法:用测试夹具重构你的C++项目(CLion实战篇)

Google Test进阶实战&#xff1a;用测试夹具重构复杂C项目的工程化实践 当你的C项目从几百行扩展到几万行代码时&#xff0c;那些曾经简单的单元测试开始变得力不从心。测试用例之间出现隐蔽的状态依赖&#xff0c;setup代码重复率飙升&#xff0c;而每次运行测试套件的时间越来…...

宝塔面板新手避坑指南:从服务器选购到LNMP环境一键部署全流程

宝塔面板新手避坑指南&#xff1a;从服务器选购到LNMP环境一键部署全流程 第一次接触服务器运维的新手&#xff0c;往往会被各种专业术语和复杂操作搞得晕头转向。作为过来人&#xff0c;我深知那种面对命令行时的无助感。宝塔面板的出现&#xff0c;确实让服务器管理变得简单了…...

探索开源字体商用解决方案:思源宋体TTF的多场景应用与价值解析

探索开源字体商用解决方案&#xff1a;思源宋体TTF的多场景应用与价值解析 【免费下载链接】source-han-serif-ttf Source Han Serif TTF 项目地址: https://gitcode.com/gh_mirrors/so/source-han-serif-ttf 副标题&#xff1a;免费商用授权与多场景适配的专业中文字体…...

CCMusic跨平台部署指南:Windows/Linux/macOS全适配

CCMusic跨平台部署指南&#xff1a;Windows/Linux/macOS全适配 音乐风格识别从未如此简单——无论你用哪种电脑系统 1. 开篇&#xff1a;为什么需要跨平台部署方案 还在为音乐风格分类工具的安装头疼吗&#xff1f;不同的操作系统、不同的环境配置、复杂的依赖关系...这些麻烦…...

革命性LLM优化代理OptiLLM:零训练实现2-10倍推理性能提升

革命性LLM优化代理OptiLLM&#xff1a;零训练实现2-10倍推理性能提升 【免费下载链接】optillm Optimizing inference proxy for LLMs 项目地址: https://gitcode.com/gh_mirrors/op/optillm OptiLLM是一款强大的LLM优化代理工具&#xff0c;能够在不进行任何模型训练的…...

StarVCenter单机版安装避坑指南:从BIOS设置到虚拟机创建的完整流程

StarVCenter单机版安装全流程实战&#xff1a;从硬件准备到虚拟机管理的深度解析 在当今企业IT基础设施快速迭代的背景下&#xff0c;虚拟化技术已成为资源整合与管理的核心解决方案。StarVCenter作为一款国产化虚拟化管理平台&#xff0c;其单机版部署方案特别适合中小型业务场…...

AI生成内容检测新思路:除了红绿词表,我们还能用哪些方法识别ChatGPT写的文章?

AI生成内容检测技术全景&#xff1a;超越红绿词表的七种实战方法 当ChatGPT生成的论文摘要通过学术评审、AI撰写的新闻稿被主流媒体刊发时&#xff0c;内容真实性的边界正在变得模糊。某高校教授最近向我展示了一份学生作业——文笔流畅的哲学论述&#xff0c;最终被证实完全由…...

Java 技术:稳定性与创新性融合下的持续卓越之路

【导语&#xff1a;在科技变革与挑战并存的当下&#xff0c;Java 凭借独特优势保持显著地位。它在稳定性与创新性间寻得平衡&#xff0c;通过社区治理、开源框架等方面不断发展&#xff0c;未来发展值得期待。】JCP 驱动的 Java 社区民主治理Java 成功的核心在于其充满活力的社…...

别再乱用Adam了!PyTorch中AdamW优化器的正确打开方式(附代码示例)

别再乱用Adam了&#xff01;PyTorch中AdamW优化器的正确打开方式&#xff08;附代码示例&#xff09; 当你盯着训练曲线发呆&#xff0c;发现验证集表现始终不如预期时&#xff0c;或许该检查一下优化器的选择了。很多开发者习惯性地在PyTorch脚本里写下optim.Adam(model.para…...