蓝桥杯DP算法——背包问题（C++）

目录

一、01背包问题

二、完全背包问题

三、多重背包问题

四、多重背包问题（优化版）

五、分组背包问题

一、01背包问题

01背包问题就是有N件物品，一个空间大小为V的背包，每个物品只能使用一次，使得背包中所装物品的价值总和最大。

  如图所示使用一个二维数组来存放从前i个物品中取，总体积不超过j的包中价值最大值。

 根据图二所示，我们可以将每次dp到的情况分为两种，一种是选择第 i 件物品，另一种是不选择第 i 件物品。

  • （不含 i ）就是从0~i-1中选择体积不超过 j 的物品，也就是f(i-1,j)
  • （含 i ）即从 1 ~ i 中选，包含 i，且总体积不超过 j。可以先把第 i 个物品拿出来，即从第 1 ~ i-1中选，且总体积不超过 j-v[i]，也就是f(i-1,j-v_{i})+w_{i}

最终：f[ i ][ j ] = max(f[ i-1 ][ j ], f[i-1][j-v[ i ]] +w[ i ]

例题：https://www.acwing.com/problem/content/2/

朴素做法： 

#include<iostream>
using namespace std;
const int N=1010;
int v[N],w[N];
int f[N][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=1;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]);
            }
        }
    }
    
    
    cout<<f[n][m];
    
    return 0;
}

优化： 

 f[i] 只用到了 f[i-1] 这一层，即 f[i-2] 到 f[0] 对 f[i] 是没有用的，所以第二层循环可以直接从 v[i] 开始

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

 从二维优化成一维（空间优化）

如果直接删除掉 f[i] 这一维即

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

但是这样直接删掉是错误，因为j是递增的。

原式：f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);

改成一维：f[j] = max(f[j], f[j - v[i]] + w[i]);

由于 f[i][] 只跟上一状态（f[i - 1][]）有关 上面两个式子 ：这一状态（左） = 上一状态（右）

即 f[i][j] 是由 f[i - 1][j - v[i]] 推出来的 现在进行空间优化，那么必须要保证 f[j] 要由 f[j - v[i]] 推出来的。

如果j层循环是递增的，则相当于 f[i][j] 变得是由 f[i][j - v[i]] 推出来的， 而不是 f[i - 1][j - v[i]] 推出来的。

优化后代码：

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

二、完全背包问题

完全背包不同于01背包的是，每件物品都是无限使用的。

如图所示，与01背包相似的是每次选择0,1,2,3,4,5，....k个

不选时仍是 f[ i-1][ j ]

选择k件时是 f[ i-1][ j-k*v[i]] +k*w[i]

也就是：

                                                         f[ i-1][ j-k*v[i]] +k*w[i]

 例题：https://www.acwing.com/problem/content/3/

朴素写法： 

#include<iostream>
using namespace std;

const int N=1010;
int n,m;
int v[N],w[N],f[N][N];

int main()
{
    cin>>n>>m;
    for(int i=i;i<=n;i++) scanf("%d%d",&v[i],&w[i]);
    
    for(int i=1;i<=n;i++)
    {
        for(int j=1;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]]+w[i]*k);
            }
        }
    }
    
    cout<<f[n][m];
    return 0;
}

优化：

在对完全背包问题优化时，我们由图公式可知f[i][j]可以简化为max(f[i-1][j],f[i][j-v]+w)

优化后代码：

#include <iostream>
#include <algorithm>

using namespace std;

const int N=1010;
int f[N];
int v[N],w[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=v[i];j<=m;j++)
        {
            f[j]=max(f[j],f[j-v[i]]+w[i]);
        }
    }

    cout<<f[m];

    return 0;
}

三、多重背包问题

多重背包问题相较于之前的问题就是每个物品是有限s个。 

例题：https://www.acwing.com/problem/content/4/

#include<iostream>
using namespace std;
const int N=110;

int n,m;
int s[N],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]>>s[i];
    
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=m;j++)
        {
            for(int k=0;k<=s[i]&&j>=(k*v[i]);k++)
            {
                    f[i][j]=max(f[i][j],f[i-1][j-v[i]*k]+w[i]*k);
            }
        }
        
    }
    cout<<f[n][m];
    return 0;
}

四、多重背包问题（优化版）

首先我们以之前完全背包问题的优化方法尝试使用另一个表达式来代替，但是结果如图所示，不是很好解决。 

二进制法优化：二进制优化的方法在于使用二进制的表示方式来代替每个物品的个数，当某件物品的个数很多的时候无需从1遍历循环到n，可以将其分解成log_{_{2}^{}}^{n}个位权来表示。

为了方便理解举个例子：

如果要拿1001次苹果，传统就是要拿1001次；二进制的思维，就是拿7个箱子就行（分别是装有512、256、128、64、32、8、1个苹果的这7个箱子）,这样一来，1001次操作就变成7次操作就行了。

但是要注意的一点是如果某件物品的个数不是二次幂减一，就将前一位的值与s差值记为下一个位权。这样就可以表示0~s之内的所有数了。

然后就将问题分解成为了，01背包问题。

例题：https://www.acwing.com/problem/content/5/

#include<iostream>
using namespace std;

const int N=11010,M=2010;
int v[N],w[N];
int f[N];

int main()
{
    int n,m;
    cin>>n>>m;
    
    int cnt=0;
    while(n--)//初始化v[] w[]
    {
        int a,b,s;
        cin>>a>>b>>s;
        int k=1;
        while(k<=s)
        {
            cnt++;
            v[cnt]=a*k;
            w[cnt]=b*k;
            s-=k;
            k*=2;
        }
        
        if(s>0)
        {
            cnt++;
            v[cnt]=a*s;
            w[cnt]=b*s;
        }
        
        
    }
    n=cnt;
    //01背包
    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;
}

五、分组背包问题

分组背包问题的不同于之前背包问题的地方在于分组背包是将物品分成几组，然后再在每组里面选择一个物品，并且每组只能选择一个物品。

这里的dp状态计算与之前的也有所不同，这里表示的是第i组选哪一个，f[i-1][j]是表示不选择这一组的物品，f[i-1][j-v[i,k]]+w[i,k]表示的是这一组中选择哪一个。 

例题： https://www.acwing.com/problem/content/9/

#include<iostream>
using namespace std;

const int N=110;
int n,m;
int s[N],v[N][N],w[N][N];
int f[N];

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>s[i];
        for(int j=1;j<=s[i];j++)
        {
            cin>>v[i][j]>>w[i][j];
        }
    }
    
    for(int i=1;i<=n;i++)
    {
        for(int j=m;j>=0;j-- )
        {
            for(int k=0;k<=s[i];k++)
            {
                if(v[i][k]<=j)
                {
                    f[j]=max(f[j],f[j-v[i][k]]+w[i][k]);
                }
            }
        }
    }
    
    
    cout<<f[m];
    return 0;
}

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

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

阿里云香港服务器cn2速度测试和租用价格表

阿里云香港服务器cn2速度测试和租用价格表

阿里云香港服务器中国香港数据中心网络线路类型BGP多线精品&#xff0c;中国电信CN2高速网络高质量、大规格BGP带宽&#xff0c;运营商精品公网直连中国内地&#xff0c;时延更低&#xff0c;优化海外回中国内地流量的公网线路&#xff0c;可以提高国际业务访问质量。阿里云服务…
阅读更多...
通过eeprom验证FPGA实现的单字节/页读写IIC接口时序

通过eeprom验证FPGA实现的单字节/页读写IIC接口时序

1、概括 前文设计基于FPGA的IIC接口模块&#xff0c;本文将使用eeprom来验证该模块的设计。为了便于查看读写波形&#xff0c;采用两个按键来控制对eeprom数据的读写&#xff0c;当按键0按下后&#xff0c;FPGA向eeprom的前64个存储地址写入地址对应的数据&#xff0c;当按键1按…
阅读更多...
安卓实现简单砸地鼠游戏

安卓实现简单砸地鼠游戏

效果 布局 <LinearLayout xmlns:android"http://schemas.android.com/apk/res/android"xmlns:app"http://schemas.android.com/apk/res-auto"xmlns:tools"http://schemas.android.com/tools"android:layout_width"match_parent"a…
阅读更多...
前端秘法进阶篇----这还是我们熟悉的浏览器吗?(浏览器的渲染原理)

前端秘法进阶篇----这还是我们熟悉的浏览器吗?(浏览器的渲染原理)

目录 一.浏览器渲染原理 二.渲染时间点 三.渲染流水线 1.解析html(Parse HTML) 1.1解析成DOM树(document object model) 1.2解析成CSSOM树(css object model) 2.样式计算(Recalculate Style) 3.布局(Layout) 4.分层(Layer) 5. 绘制(Paint) 6.分块(Tiling) 7. 光栅化…
阅读更多...
永久禁止windows自动更新方法

永久禁止windows自动更新方法

文章目录 前言一、打开本地组策略编辑器二、禁用windows更新总结 前言 每次打开电脑&#xff0c;右下角就会弹出设备更新提示&#xff0c;看着令人烦恼&#xff0c;并且更新可能导致电脑设置发生改变甚至是卡顿&#xff0c;所以为了自己方便于是出了禁用电脑更新的办法&#x…
阅读更多...
作用域基本使用

作用域基本使用

基本使用 1.在java编程中&#xff0c;主要的变量就是属性&#xff08;成员变量&#xff09;和局部变量 2.局部变量一般指的是在成员方法中定义的变量 3.java中作用域的分类 全局变量&#xff1a;也就是属性&#xff0c;作用域为整个类体 局部变量&#xff1a;也就是除了属性之外…
阅读更多...
树莓派：使用mdadm为重要数据做RAID 1保护

树莓派：使用mdadm为重要数据做RAID 1保护

树莓派作为个人服务器可玩性还是有点的。说到服务器&#xff0c;在企业的生成环境中为了保护数据&#xff0c;基本上都会用到RAID技术。比如&#xff0c;服务器两块小容量但高性能的盘做个RAID-1按装操作系统&#xff0c;余下的大容量中性能磁盘做个RAID-5或者RAID-6存放数据。…
阅读更多...
七、ActiveMQ的传输协议

七、ActiveMQ的传输协议

ActiveMQ的传输协议 一、是什么二、协议1.TCP(默认)2.NIO3.AMQP4.STOMP5.SSL6.MQTT7 WS 三、NIO配置案例1.修改activemq.xml2.重启3.生产者/消费者4.性能提升4.1 配置4.2 生产者/消费者 一、是什么 官网地址&#xff1a;http://activemq.apache.org/configuring-version-5-tra…
阅读更多...
工程师日常：海丰县附城镇鹿境元宵开灯活动

工程师日常：海丰县附城镇鹿境元宵开灯活动

海丰县附城镇鹿境元宵开灯活动 &#xff08;蔡惠进搜集整理&#xff09; 鹿境乡春节正月初十大老热&#xff0c;全县家喻户晓。为纪念先祖功德&#xff0c;在本乡车地建立蔡氏“济阳堂”大祖祠&#xff0c;并定年初十为开灯日&#xff0c;大祖开灯代代相传。凡移居外乡裔孙、“…
阅读更多...
Arrays类及其API

Arrays类及其API

Arrays是用来操作数组的一个工具类 import java.util.Arrays; import java.util.Comparator; import java.util.function.IntToDoubleFunction;public class Test {public static void main(String[] args) {//1.以字符串形式返回数组的内容int[] arr {10,20,30,40,50,60};Sy…
阅读更多...
书生浦语大模型实战营-课程笔记（4）

书生浦语大模型实战营-课程笔记（4）

微调分为两种&#xff0c;增量预训练和指令跟随。 指令跟随微调&#xff1a; 1.只对答案计算Loss 2.训练时数据为一问一答的形式&#xff08;input和output&#xff09; 增量预训练&#xff1a; 只需要output的数据进行训练 xtuner:微调框架 操作部分的笔记参考git上的文档…
阅读更多...
网页端、APP端页面国际化-多语言翻译与半自动比对程序

网页端、APP端页面国际化-多语言翻译与半自动比对程序

网站和APP国际化翻译过程中&#xff0c;对多语言配置文件的翻译与比对模板&#xff0c;记录工作经验。 最佳的模式是&#xff1a;前期尽量做好全部菜单按钮多语言TS配置文件&#xff0c;网页端、APP端和管理端使用同一个配置文件&#xff0c;比如buttons.ts,menus.ts&#xff…
阅读更多...
PHP服务商微信支付分支付（需确认模式）

PHP服务商微信支付分支付（需确认模式）

//查询支付分是否支付 public function serviceorderServiceorder($out_order_no) {$setting [];$service_id $setting[service_id];$sub_mchid $setting[mchid];$ps "/v3/payscore/partner/serviceorder?service_id${service_id}&sub_mchid${sub_mchid}&out…
阅读更多...
【PyQt】14-绘图-QPainter

【PyQt】14-绘图-QPainter

文章目录 前言一、QPainter二、绘制文本-drawTextQt里面的文本对齐方式 运行结果 三、像素点总结 前言 1、学会画图方法 一、QPainter 通常可以绘制文本、各种图形&#xff08;点、线、椭圆、弧、扇形、多边形等等&#xff09;、图像。 必须在painrEvent事件方法中绘制各种元…
阅读更多...
CES 2024：NVIDIA 通过新的笔记本电脑、GPU 和工具提供生成式 AI

CES 2024：NVIDIA 通过新的笔记本电脑、GPU 和工具提供生成式 AI

在 CES 2024 上&#xff0c;NVIDIA 推出了一系列硬件和软件&#xff0c;旨在释放 Windows 11 PC 上生成式 AI 的全部潜力。 在 PC 上本地运行生成式 AI 对于隐私、延迟和成本敏感型应用程序至关重要。在 CES 上&#xff0c;NVIDIA 将在整个技术堆栈中带来新的创新&#xff0c;…
阅读更多...
MATLAB导出图程序

MATLAB导出图程序

本文将以代码的形式快速介绍MATLAB导出图到Paper 1 从simulation导出数 2 与simulation同源文件夹下创建导图m文件 代码如下&#xff1a; % 实验后的数据处理用 M-文件 % clear all % 清空工作空间 % close all　　　　　　% 关闭所有图形窗口 % load adp.mat …
阅读更多...
双指针算法+例题

双指针算法+例题

1、性质 双指针算法&#xff0c;实质上是把朴素算法O&#xff08;n^2),发现一些性质&#xff0c;转换成 O&#xff08;N&#xff09;时间复杂度。 2、图解核心思想 3、代码模板 for(int i0,j0;i<n;i) {while(j<i && check(i,j)) j;//每道题目的具体逻辑 } 4…
阅读更多...
对树莓派上配置mdadm的一些补充

对树莓派上配置mdadm的一些补充

1、如果要重新配置该如何回退到初始状态&#xff1f; 答&#xff1a;可参考以下指令&#xff1a; cat /proc/mdstat sudo umount /dev/md0 sudo mdadm --stop /dev/md0 sudo mdadm --zero-superblock /dev/sda sudo mdadm --zero-superblock /dev/sdb sudo nano /etc/fstab&a…
阅读更多...
ModuleNotFoundError: No module named ‘torchvision.models.utils‘报错的一种解决方法

ModuleNotFoundError: No module named ‘torchvision.models.utils‘报错的一种解决方法

最近在做一个BEV项目&#xff0c;在配置环境的时候&#xff0c;遇到了报错的一个问题&#xff1a; ModuleNotFoundError: No module named ‘torchvision.models.utils’ 我开始以为是我没有安装torchvision pip install torchvision -i http://pypi.douban.com/simple输入这…
阅读更多...
CSS-基础-MDN文档学习笔记

CSS-基础-MDN文档学习笔记

CSS构建基础 查看更多学习笔记&#xff1a;GitHub&#xff1a;LoveEmiliaForever MDN中文官网 CSS选择器 选择器是什么 CSS 选择器是 CSS 规则的第一部分&#xff0c;它用来选择HTML元素&#xff0c;选择器所选择的元素&#xff0c;叫做选择器的对象 选择器列表 如果有多…
阅读更多...
最新文章

Copyright @ 2022~2023