01背包问题 刷题笔记

news/2024/4/23 21:43:34/文章来源:https://blog.csdn.net/2301_78763076/article/details/136547897

思路 dp
用f[i][j]来表示当体积为j时 考虑前i件物品可以获得的 最大值 
记住f[i][j]本身是个价“价值” 
考虑两种状态 是否将第i件物品放入背包里面
将背包的体积从小到大递增来进行考虑
首先 考虑条件 如果当前增加的体积放不下下一件物品 
则该体积 可以获得的最大值可以直接继承上一个f[i-1][j] 
如果可以放下 则比较 放入与不放入谁获得的值较大
即 f[i-1][j]与f[i-1][j-v[i]]+w[i]比较
 //-v[i]是为了减去放入后的背包体积
 加w[i]是为了加上放入后获得的价值
 每一次存下的 都是基于考虑到当前物品 的最优选择
 比方说 前面已经进行了i件物品的选择 
 获得了一个基于i件物品的最大值
  这时候 第i+1件物品突然出现 体积为1,价值1000000;
  那么当背包体积只有1时的最大值会立刻被更新成100000;
  此时仍然是最优选择
  代码

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
const int N=1010;
int f[N][N];
int w[N],v[N];
int n,m;
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=1;j<=m;j++){
            if(j<v[i]){
            f[i][j]=f[i-1][j];
            }else{
                f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i]);
            }
            
        }
    }
    cout<<f[n][m];
    return 0;
}

优化思路

二维到一维 

我们发现 考虑第i件物品时的最大值来自前面一层i-1件物品的最大值

也就是说 所有的当前层 都只来自上一层的最大值

而上上层已经不重要了

因此有没有可能直接删掉层数记录

观察发现f[i][]是从f[i-1][]这一层更新出来的

此时我们直接删除i

只使用j

观察式子f[j-v[i]]+w[i]

也就是说 如果我们逆序更新的话 需要使用和比较的数是j-v[i]

这个数是绝对小于j的 如果将j从m往0更新

保证了更新时只有大于等于j的数被覆盖掉了

而我们需要用的 j-v[i]则被保留下来

举例

如果我们逆序更新的话

假设 原来 f[j](1-5)是

1 2 5 7 9

然后我们逆序更新

for(int i=0;i<n;i++){
        for(int j=m;j>=v[i];j--){
            f[j]=max(f[j],f[j-v[i]]+w[i]);
        }
    }

假设 此时j=5,v[i]=2,    f[j-v[i]]+w[i]=11那么

我们和上一个f[3]比较 比较完了以后将上一个f[5]覆盖掉

此时f[j](1-5)的情况为

1 2 5 7 11

然后当j=4;

v[i]=1;

f[j-v[i]]+w[i]=9;

即我们需要用的是f[3]

此时f[3]并没有被污染 

执行以后

f[j](1-5)的情况为

1 2 5 9 11

以此类推我们的目的达到了

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int f[N];
int w[N],v[N];
int j[N]; 
int n,m;
int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++){
        //int x,y;
        cin>>v[i]>>w[i];
        //v[i]=x;
        //w[i]=y;
    }
    for(int i=0;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;

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_997442.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

c++复习

基础 内存分区 栈&#xff1a; 存放函数的局部变量、函数参数、返回地址等&#xff0c;由编译器自动分配和释放。 堆&#xff1a; 动态申请的内存空间&#xff0c;就是由 malloc 分配的内存块&#xff0c;由程序员控制它的分配和释放&#xff0c;如果程序执行结束还没有释放…

YOLO-World:实时开放词汇目标检测

摘要 Open Vocabulary&#xff1a;开放词汇 论文链接&#xff1a;https://arxiv.org/pdf/2401.17270.pdf You Only Look Once (YOLO) 系列检测器已经确立了自己作为高效和实用工具的地位。然而&#xff0c;它们对预定义和训练过的对象类别的依赖限制了它们在开放场景中的适用…

在多文件编译时,如果模板类的成员函数的定义和模板类不在一个文件下会怎么样?

编译器将找不到成员函数的定义&#xff0c;哪怕你将存放成员函数定义的test.cpp一块编译&#xff0c;编译器也无法找到该模板类的成员函数的定义。 正确的做法是&#xff1a; 将模板类的声明和成员函数定义都定义在.h文件下

数位dp 笔记

小技巧1:求区间[X, Y]可以转换为求F(Y) - F(X-1) F(X)表示0~X中满足条件的数字个数 小技巧2&#xff1a;可以用树的形式来看 遍历最高位&#xff0c;每一位分为两种情况&#xff1a;未达到上界和达到上界 如果走到右边最底端需加1 度的数量 求给定区间 [X,Y]中满足下列条件的…

Linux——线程同步互斥(线程安全)

线程互斥 进程线程间的互斥相关背景概念 临界资源&#xff1a;多线程执行流共享的资源就叫做临界资源临界区&#xff1a;每个线程内部&#xff0c;访问临界资源的代码&#xff0c;就叫做临界区互斥&#xff1a;任何时刻&#xff0c;互斥保证有且只有一个执行流进入临界区&…

System Verilog学习笔记(十八)——线程控制

线程控制 发生器把激励传给代理时&#xff0c;环境类需要知道发生器什么时候完成任务&#xff0c;以便及时终止测试平台中还在运行的线程&#xff0c;这个过程就需要借助线程间的通信来完成。常用的线程间通信有事件控制、wait语句、SV信箱和旗语等。 Verilog对语句有两种分组…

SpringCloud-数据认证加密总结

一、数据加密认证介绍 在当今分布式系统的日益复杂和信息传递的广泛网络化环境中&#xff0c;确保通信的安全性至关重要。数据的加密和认证作为保障信息传递安全的关键手段&#xff0c;在分布式系统中扮演着不可或缺的角色。Spring Cloud&#xff0c;作为一套构建微服务架构的…

几个市场主流伦敦银交易系统简介

很多人在伦敦银交易中都希望建立一个交易系统&#xff0c;依靠这个系统&#xff0c;我们在市场中能够建立稳定盈利的基础。下面我们就来简单地介绍几个市场主流的伦敦银交易系统。 均线交易系统。这是很多人使用的伦敦银交易系统&#xff0c;一般适用于趋势行情中。均线交易系统…

Java精品项目--第5期基于SpringBoot的高速收费系统的设计分析与实现

项目使用技术栈 SpringBootMavenShiroMySQLMybatis-PlusJavaJDK1.8HTML 系统介绍 项目截图

Docker部署ruoyi前后端分离项目

目录 一. 介绍前后端项目 二. 搭建局域网 2.1 创建网络 2.2 注意点 三. Redis 3.1 安装 3.2 配置redis.conf文件 3.3 测试 四. 安装MySQL 4.1 安装 4.2 配置my2.cnf文件 4.3 充许远程连接 五. 若依部署后端服务 5.1 数据导入 5.2 使用Dockerfile自定义镜像 5.3 运行…

010-内存泄露

内存泄露 概念引起内存泄漏原因解决排查方案 概念 系统进程不再用到的内存&#xff0c;没有及时释放&#xff0c;就叫做内存泄漏&#xff08;memory leak&#xff09;。当内存占用越来越高&#xff0c;轻则影响系统性能&#xff0c;重则导致进程崩溃。 引起内存泄漏原因 全局…

突破编程_前端_JS编程实例(网站标题栏TAB组件)

1 开发目标 实现如下网站标题栏 TAB 组件&#xff1a; 在点击"页面2"选项卡后&#xff0c;TAB 组件会切换对应的面板&#xff1a; 2 详细需求 网站标题栏 TAB 组件该组件需根据客户端提供的参数创建&#xff0c;具备动态构建 TAB 区域、选项卡切换及自定义内容…

Redis(5.0)

1、什么是Redis Redis是一种开源的、基于内存、支持持久化的高性能Key-Value的NoSQL数据库&#xff0c;它同时也提供了多种数据结构来满足不同场景下的数据存储需求。 2、安装Redis&#xff08;Linux&#xff09; 2.1、去官网&#xff08;http://www.redis.cn/&#xff09;下…

腾讯云哪款服务器最便宜划算?2024腾讯云服务器优惠价格表

腾讯云优惠活动2024新春采购节活动上线&#xff0c;云服务器价格已经出来了&#xff0c;云服务器61元一年起&#xff0c;配置和价格基本上和上个月没什么变化&#xff0c;但是新增了8888元代金券和会员续费优惠&#xff0c;腾讯云百科txybk.com整理腾讯云最新优惠活动云服务器配…

图书馆管理系统(2)

接下来实现系统的子菜单&#xff0c;在写一个子模块的时候&#xff0c;其他子模块先屏蔽起来&#xff0c;因为没实现&#xff0c;代码运行就通不过 屏蔽起来写上todo&#xff0c;后面(Ctrl键F)搜索&#xff0c;找todo来实现 先来实现图书管理模块 第一步&#xff0c;先要把图…

缺陷检测:使用PatchCore训练自己的数据集

文章目录 前期准备两种方法 演示运行结果 代码详解见缺陷检测–PatchCore的代码解读 前期准备 必须包含有训练图片&#xff08;无缺陷图片&#xff09;、测试图片&#xff08;缺陷图片&#xff09;和ground_truth&#xff0c;并且ground_truth必须与对应图片的名称相同。 本文…

MCU中断里使用软延时函数delay_ms(u16 x)问题及实例探讨

原贴有误已删&#xff1a;https://blog.csdn.net/weixin_50007421/article/details/136138221 今天完善如下&#xff1a; 本意&#xff1a;只是想表达“复杂系统中断里当然尽量不用软延时函数&#xff0c;但简单系统只要心中有数逻辑清楚实测无妨就完全可行”。 但后来感觉还…

H264的打包,nal,es,pes,pts,dts,ps,ts

编码层次 视频编码层&#xff1a;预测、变换、量化、熵编码等操作slice层&#xff1a;将视频帧分割成若干个编码单元&#xff0c;包含一定数量的宏块&#xff0c;提高编解码的并行性和容错性。NAL层&#xff1a;提升对网络传输和数据存储的亲和性 视频编码层 基准-Baseline …

火柴排队(逆序对 + 离散化)

505. 火柴排队 原题链接 思路 如下是画图分析的一些过程 在这里贪心的思路是排序&#xff0c;然后两个数组都是从小到大那样对应的话最终的答案可达到最小 而我们只能交换相邻的火柴&#xff0c;故在这里先假设一个简化版本&#xff0c;即A有序&#xff0c;而只需要对B进行…

HTML+CSS+BootStrap游乐园官网

一、技术栈 支持pc、pad、手机访问&#xff0c;页面自适应&#xff01;&#xff01; html5cssbootstrapjs 二、项目截图 接受项目定制&#xff0c;站内联系博主&#xff01;&#xff01;&#xff01;