01背包详解，状态设计，滚动数组优化，通用问题求解

文章目录

  • 0/1背包
    • 前言
    • 一、0/1背包的状态设计
      • 1、状态设计
      • 2、状态转移方程
      • 3、初始状态
      • 4、代码实现
      • 5、滚动数组优化
        • 二维优化为两个一维
        • 二维优化为一个一维，倒序递推
    • 二、0/1背包的通用问题
      • 求最大值
      • 求最小值
      • 求方案数

0/1背包

前言

0/1包问题，作为动态规划问题的经典问题，可以帮助捋顺思维。核心就是有一堆物品,有两个维度的限制，在保证一个维度限制的情况下，使得另一个维度最优。

一、0/1背包的状态设计

有n(n≤100)个物品和一个容量为m(m≤10000)的背包。
第i个物品的容量是c[i]，价值是w[i]。现在需要选择一些物品放入包, 总容不能超过背包容量，求能够达到的物品的最大总价值。

以上就是0/1背包问题的完整描述,之所以叫0/1背包，因为每种物品只有一个,可以选择
放入背包或者不放，而0代表不放，1 代表放。

1、状态设计

状态(i, j)表示前i个物品恰好放入容量为j的背包(0≤i<n，0≤j≤m);
令dp表[][]示状态(i, j)下该背包得到的最大价值，即前i个物品恰好放入容量为j的背包所得
到的最大总价值;

2、状态转移方程

列出状态转移方程如下:
d p [ i ] [ j ] = m a x ( d p [ i − 1 ] [ j ] , d p [ i − 1 ] [ j − c [ i ] ] + w [ i ] ) dp[i][j] = max(dp[i-1][j], dp[i-1][j - c[i]] + w[i]) dp[i][j]=max(dp[i−1][j],dp[i−1][j−c[i]]+w[i])
因为每个物品要么放,要么不放,所以只需要考虑第i个物品放或不放的情况:

1)不放:如果第i个物品不放入容量为j的背包",那么问题转化成求"前i-1 个物品放入容为j的背包"的问题;于不放,所以最大价值就等于"前i-1个物品放入容量为j的背包"的最大价值，即dp[i-1][j];

2)放:如果"第i个物品放入容为j的背包"，那么问题转化成求"前i-1个物品放入容量为j-c[j]的背包"的问题;那么此时最大价值就等于"前i-1个物品放入容为j-c[i] 的背包"的最大价值加上放入第i个物品的价值,即dp[i-1][j - c[i]] + w[i]
将以上两种情况取大者,就是我们所求的“前i个物品恰好放入容量为j的背包"的最大价值了。

在这里插入图片描述

3、初始状态

我们发现，当状态在进行转移的时候，dp(i, j)不是来自dp(i - 1 , j),就是来自dp(i - 1 , j - c[i])，所以必然有一个初始状态，而这个初始状态就是(0, i)，含义是"前i个物品放入一个容量为0的背包"，这个状态下的最大价值为0,即dp[0][i] = 0;

img

4、代码实现

铺垫了那么多，我们来实现一下0/1背包的板子。

//#define N 110
//#define M 1010
//int dp[N][M]{0}, c[N]{0}, w[N]{0}, n, m;
//c[i]为第i个物品的重量，w[i]为第i个物品的价值。n、m分别为物品数和背包容量
for (int i = 1; i <= n; i++)
    for (int j = 0; j <= m; j++)
        if (j < c[i])
            dp[i][j] = dp[i - 1][j];
        else
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - c[i]] + w[i]);

5、滚动数组优化

滚动数组优化为递推问题中的常用空间优化手段，如果每次递推都由上一次状态转移那么我们可以将空间降低一个维度。

我们再看状态转移图

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

发现每个状态都只跟上一行同一列和上一行左边的状态有关，我们可以开两个一维数组，分别保存上一行和当前行的状态，当然也可以只用一个一维数组然后倒序递推来实现。

二维优化为两个一维

两个一维数组一个保存上一行的状态一个保存当前行状态即可。

#define N 110
#define M 1010
int dp1[M]{0}, dp2[M]{0}, c[N]{0}, w[N]{0}, n, m;
for (int i = 1; i <= n; i++)
    cin >> c[i] >> w[i];
for (int i = 1; i <= n; i++)
{
    for (int j = 0; j <= m; j++)
        if (j < c[i])
            dp2[j] = dp1[j];
        else
            dp2[j] = max(dp1[j], dp1[j - c[i]] + w[i]);
    memcpy(dp1, dp2, sizeof(dp1));
}
cout << dp2[m];
二维优化为一个一维，倒序递推

即然每次状态都只由上一行当前列和当前行左侧列转移，我们发现两个一维优化方案中，dp1其实是也可以优化掉的，假如只剩下一个一维数组dp，如果我们正序递推会怎样？

初始时dp中存储上一次状态转移的数据，如果正序递推则导致我们状态转移需要上一次状态但是由于正序递推覆盖了左侧内容，就无法获取上一次状态了，所以我们选择逆序递推：

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

#define N 110
#define M 1010
int dp[M]{0}, dp2[M]{0}, c[N]{0}, w[N]{0}, n, m;
for (int i = 1; i <= n; i++)
    cin >> c[i] >> w[i];
for (int i = 1; i <= n; i++)
{
    for (int j = m; j >= c[i]; j--)
            dp[j] = max(dp[j], dp[j - c[i]] + w[i]);
}
cout << dp[m];

二、0/1背包的通用问题

求最大值

原题链接

[P1048 NOIP2005 普及组] 采药 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

01背包板子题，读完数据跑一遍板子，输出数据即可。

#include <iostream>
#include <cstring>
#include <vector>
#include <functional>
#include <algorithm>
#include <cmath>
#include <functional>
#include <climits>
#include <bitset>
#include <stack>
#include <cstring>
using namespace std;
#define N 110
#define M 1010
int dp[M]{0}, c[N]{0}, w[N]{0}, n, m;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);

    cin >> m >> n;
    for (int i = 1; i <= n; i++)
        cin >> c[i] >> w[i];
    for (int i = 1; i <= n; i++)
    {
        for (int j = m; j >= c[i]; j--)
            dp[j] = max(dp[j], dp[j - c[i]] + w[i]);
    }
    cout << dp[m];
    return 0;
}

[P1060 NOIP2006 普及组] 开心的金明 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

同样是01板子题，只不过物品价值变成了重量乘价值

#include <iostream>
#include <cstring>
#include <vector>
#include <functional>
#include <algorithm>
#include <cmath>
#include <functional>
#include <climits>
#include <bitset>
#include <stack>
#include <cstring>
using namespace std;
#define N 30010
#define M 100000000
int dp[M]{0}, c[N]{0}, w[N]{0}, n, m;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);

    cin >> m >> n;
    for (int i = 1; i <= n; i++)
        cin >> c[i] >> w[i], w[i] *= c[i];

    for (int i = 1; i <= n; i++)
    {
        for (int j = m; j >= c[i]; j--)
            dp[j] = max(dp[j], dp[j - c[i]] + w[i]);
    }
    cout << dp[m];
    return 0;
}

P3985 不开心的金明 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

在不考虑内存的情况下显然是一道01背包板子题，但是你这个1e9的背包内存肯定会爆，内存不爆你时间复杂度也会爆，但是金明妈妈限制了物品重量极差不超过3（感谢金明妈妈！！！！），我们就可以将物品重量离散化到1，2，3，4上，即我们记录最小重量mi，再令每个重量减去(mi - 1)，这样物品重量就变为了1，2，3，4

由于物品数目最多100，所以物品总重量最大也就400，我们离散化后再去跑01背包的板子即可

但是！！！

有一个问题，你怎么根据离散化后的重量计算离散化前的重量呢？看我们的板子

for (int i = 1; i <= n; i++)
{
    for (int j = sum; j >= c[i]; j--)
        dp[j] = max(dp[j], dp[j - c[i]] + w[i]);
}

此时j为离散化后的重量了，你怎么确定你上面的状态方程就合法呢？如果一共给了m的空间，你此时的j对应实际重量为j + cnt * mi，cnt为装的物品数目，故而我们需要给dp增加一个维度来记录装入的物品数目

dp[i][j]就代表容量i装入了j个物品的最大价值，此时装入总重量不超过i + j * mi，（不超过是因为i可能大于j个物品的离散重量）

这样一来我们的空间复杂度只有1e2量级，时间复杂度只有1e6量级

代码如下：

#include <iostream>
#include <cstring>
#include <vector>
#include <functional>
#include <algorithm>
#include <cmath>
#include <functional>
#include <climits>
#include <bitset>
#include <stack>
#include <cstring>
using namespace std;
#define N 110
#define M 550
int dp[M][N]{0}, c[N]{0}, w[N]{0}, n, m, mi = INT_MAX, sum = 0, ans = 0;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> c[i] >> w[i], mi = min(mi, c[i]);
    mi--;
    for (int i = 1; i <= n; i++)
        c[i] -= mi, sum += c[i];

    for (int i = 1; i <= n; i++)
    {
        for (int j = sum; j >= c[i]; j--)
            for (int k = (m - j) / mi ; k >= 1; k--)
                ans = max(ans, dp[j][k] = max(dp[j][k], dp[j - c[i]][k - 1] + w[i]));
    }
    cout << ans;
    return 0;
}

求最小值

原题链接

[P1049 NOIP2001 普及组] 装箱问题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

本质还是求最大值。

在本题内，重量就是体积，价值也是体积，我们求出能装的最大体积，容量减去最大体积就是答案。

#include <iostream>
#include <cstring>
#include <vector>
#include <functional>
#include <algorithm>
#include <cmath>
#include <functional>
#include <climits>
#include <bitset>
#include <stack>
#include <cstring>
using namespace std;
#define N 50
#define M 20010
int dp[M]{0}, c[N]{0}, w[N]{0}, n, m;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);

    cin >> m >> n;
    for (int i = 1; i <= n; i++)
        cin >> c[i];
    for (int i = 1; i <= n; i++)
    {
        for (int j = m; j >= c[i]; j--)
            dp[j] = max(dp[j], dp[j - c[i]] + c[i]);
    }
    cout << m - dp[m];
    return 0;
}

求方案数

原题链接

P1164 小A点菜 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

对于本道题我们的dp[i][j]就变成了j元恰好买i道菜的方案数

对于初始状态即0元购0菜方案为1，其他0元购都是0

那么我们同样对于每道菜可以选择买或不买，可以选择用j元恰好买i - 1道菜也可以选择用j元恰好买i道菜，那么转移方程就变成了

dp[i][j] = dp[i - 1][j] + dp[i - 1][j - c[i]]

#include <iostream>
#include <cstring>
#include <vector>
#include <functional>
#include <algorithm>
#include <cmath>
#include <functional>
#include <climits>
#include <bitset>
#include <stack>
#include <cstring>
using namespace std;
#define N 110
#define M 10010
int dp[M]{0}, c[N]{0}, w[N]{0}, n, m;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> c[i];
    dp[0] = 1;
    for (int i = 1; i <= n; i++)
    {
        for (int j = m; j >= c[i]; j--)
            dp[j] += dp[j - c[i]];
    }
    cout << dp[m];
    return 0;
}

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

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

相关文章

什么是MVC？MVC框架的优势和特点

什么是MVC？MVC框架的优势和特点

目录 一、什么是MVC 二、MVC模式的组成部分和工作原理 1、模型&#xff08;Model&#xff09; 2、视图&#xff08;View&#xff09; 3、控制器&#xff08;Controller&#xff09; 三、MVC模式的工作过程如下&#xff1a; 用户发送请求&#xff0c;请求由控制器处理。 …
阅读更多...
少儿编程：从兴趣到升学的关键之路

少儿编程：从兴趣到升学的关键之路

随着科技的飞速发展&#xff0c;计算机编程已经逐渐渗透到我们生活的方方面面。对于新时代的少儿来说&#xff0c;掌握编程技能不仅可以开拓视野&#xff0c;提高思维能力&#xff0c;还可能成为他们未来升学和就业的重要砝码。6547网将探讨如何将少儿编程从兴趣培养成一种有力…
阅读更多...
谷歌推大语言模型VideoPoet：文本图片皆可生成视频和音频

谷歌推大语言模型VideoPoet：文本图片皆可生成视频和音频

Google Research最近发布了一款名为VideoPoet的大型语言模型&#xff08;LLM&#xff09;&#xff0c;旨在解决当前视频生成领域的挑战。该领域近年来涌现出许多视频生成模型&#xff0c;但在生成连贯的大运动时仍存在瓶颈。现有领先模型要么生成较小的运动&#xff0c;要么在生…
阅读更多...
图像识别与人工智能到底是何关系？有何区别？

图像识别与人工智能到底是何关系？有何区别？

图像识别是人工智能领域的一个重要应用领域&#xff0c;它利用人工智能技术和算法来分析和理解图像内容。图像识别是使计算机能够模拟和理解人类视觉系统的能力&#xff0c;并从图像中提取出有用的信息和特征。 人工智能在图像识别中扮演着至关重要的角色&#xff0c;主要体现…
阅读更多...
【Sass】网易云动画播放器

【Sass】网易云动画播放器

简介 仿网易云播放动画 效果图 sass src/assets/style/musicPlay.sass // TODO 音乐播放器动画 // ? 动画停止class >>> .muscic-play-stop // HTML结构 // <div class"music-play"> // <div class"bg-primary"></div>…
阅读更多...
二级分销的魅力：无限裂变创造十八亿的流水

二级分销的魅力：无限裂变创造十八亿的流水

有这么一个团队&#xff0c;仅靠这一个二级分销&#xff0c;六个月就打造了十八亿的流水。听着是不是很恐怖&#xff1f;十八亿确实是一个很大的数字&#xff0c;那么这个团队是怎么做到的呢&#xff1f;我们接着往下看。 这是一个销售减脂产品的团队。不靠网店&#xff0c;不…
阅读更多...
运行游戏显示缺少d3dx9_42.dll怎么办，三步即可完美解决

运行游戏显示缺少d3dx9_42.dll怎么办，三步即可完美解决

在我们使用电脑玩游戏&#xff0c;工作的时候&#xff0c;偶尔会遇到一些错误提示&#xff0c;其中之一就是缺少d3dx9_42.dll。这个错误通常出现在运行某些游戏或应用程序时&#xff0c;它表示计算机缺少了DirectX 9组件中的d3dx9_42.dll文件。为了解决这个问题&#xff0c;下面…
阅读更多...
【接口测试】Postman（三）-变量与集合

【接口测试】Postman（三）-变量与集合

一、变量 ​ 变量这个概念相信大家都不陌生&#xff0c;因此在这里我们不介绍了。主要说一下在Postman中有哪几类变量&#xff0c;主要包括以下四类&#xff1a; Global&#xff08;全局&#xff09; Environment&#xff08;环境&#xff09; Local&#xff08;本地&#xf…
阅读更多...
python打开opencv图像与QImage图像及其转化

python打开opencv图像与QImage图像及其转化

目录 1、Qimage图像 2、opencv图像 3、python打开QImage图像通过Qlabel控件显示 4、python打开QImage图像通过opencv显示 5、python打开opencv图像并显示 6、python打开opencv图像通过Qlabel控件显示 1、Qimage图像 QImage是Qt库中用于存储和处理图像的类。它可以存储多种…
阅读更多...
微软官方镜像下载大全(windows iso 官方镜像)

微软官方镜像下载大全(windows iso 官方镜像)

原本只是想下一个Windows Server 2022中文版的镜像&#xff0c;后面发现要么就是慢得一批的某盘&#xff0c;要么就是磁力&#xff0c;我想直接下载简简单单&#xff0c;找了一圈没有找到。官网下载需要注册、登录乱七八糟&#xff0c;最终终于找到下载方法了&#xff0c;适用于…
阅读更多...
大型语言模型，MirrorBERT — 将模型转换为通用词汇和句子编码器

大型语言模型，MirrorBERT — 将模型转换为通用词汇和句子编码器

大型语言模型&#xff0c;MirrorBERT — 将模型转换为通用词汇和句子编码器 一、介绍 BERT 模型在现代 NLP 应用中发挥着基础作用&#xff0c;这已不是什么秘密。尽管它们在下游任务上表现出色&#xff0c;但大多数模型在没有微调的情况下在特定问题上并不是那么完美。从原始预…
阅读更多...
（一）深入理解Mysql底层数据结构和算法

（一）深入理解Mysql底层数据结构和算法

什么是索引 索引是帮助MySQL高效获取数据的排好序的数据结构 数据结构有哪些 数据结构模拟网站&#xff1a;Data Structure Visualization 二叉树 不适合做自增ID的数据结构。如下示意图&#xff0c;假设采用二叉树作为表自增主键ID的数据存储结果如下&#xff1a;当查询i…
阅读更多...
BUG记录——drawio出现“非绘图文件 (error on line 7355 at column 83: AttValue: ‘ expected)”

BUG记录——drawio出现“非绘图文件 (error on line 7355 at column 83: AttValue: ‘ expected)”

BUG现象 drawio出现“非绘图文件 (error on line 7355 at column 83: AttValue: ’ expected)”&#xff0c;如下图&#xff1a; 解决办法 这只是我自己摸索到的解决办法并不一定适用于所以人&#xff0c;对我是适用的。 首先用记事本打开损坏的drawio文件&#xff0c;如下 …
阅读更多...
服务器经常死机怎么办？如何处理

服务器经常死机怎么办？如何处理

关于服务器死机这一话题相信大家是不会陌生的&#xff0c;平时在使用服务器的过程中&#xff0c;或多或少都是会有遇到过。轻则耽误业务开展&#xff0c;重则造成数据丢失&#xff0c;相信每个人都不想碰到服务器死机的情况。下文我也简单的介绍下服务器死机的原因以及对应的预…
阅读更多...
多个磁盘做软件raid并解决分区aligned对齐问题

多个磁盘做软件raid并解决分区aligned对齐问题

centos 服务器验证创建软件raid10数据盘&#xff0c;该机器缺少raid硬件。只能做软件raid。 /dev/sdd至/dev/sdm共10块8T磁盘&#xff0c;做raid10&#xff1b; 步骤如下&#xff1a; &#xff08;第一步&#xff09;创建raid10 事先不需要对单个磁盘做分区 10个相同数据盘创…
阅读更多...
第11章 GUI Page417~418 步骤五 支持方框 使用宏定义

第11章 GUI Page417~418 步骤五 支持方框 使用宏定义

运行效果&#xff1a; 原来的创建item的方式&#xff1a; 使用宏定义的方式&#xff1a;
阅读更多...
Corel Painter各版本安装指南

Corel Painter各版本安装指南

下载链接https://pan.baidu.com/s/1g3xrCkWmOlDwAThOkqpYlg?pwd0531 #2023版本 1.鼠标右击【Corel Painter 2023】压缩包&#xff08;win11及以上系统需先点击“显示更多选项”&#xff09;【解压到 Corel Painter 2023】。 2.打开解压后的文件夹&#xff0c;双击打开【Setu…
阅读更多...
Hadoop入门学习笔记——一、VMware准备Linux虚拟机

Hadoop入门学习笔记——一、VMware准备Linux虚拟机

视频课程地址&#xff1a;https://www.bilibili.com/video/BV1WY4y197g7 课程资料链接&#xff1a;https://pan.baidu.com/s/15KpnWeKpvExpKmOC8xjmtQ?pwd5ay8 Hadoop入门学习笔记&#xff08;汇总&#xff09; 目录 一、VMware准备Linux虚拟机1.1. VMware安装Linux虚拟机1.…
阅读更多...
Diffusion扩散模型学习：图片高斯加噪

Diffusion扩散模型学习：图片高斯加噪

高斯分布即正态分布&#xff1b;图片高斯加噪即把图片矩阵每个值和一个高斯分布的矩阵上的对应值相加 1、高斯分布 np.random.normal 一维&#xff1a; import numpy as np import matplotlib.pyplot as pltdef generate_gaussian_noise(mean, std_dev, size):noise np.ran…
阅读更多...
【智慧办公】如何让智能会议室的电子标签实现远程、批量更新信息？东胜物联网硬件网关让解决方案更具竞争力

【智慧办公】如何让智能会议室的电子标签实现远程、批量更新信息？东胜物联网硬件网关让解决方案更具竞争力

近年来&#xff0c;为了减少办公耗能、节能环保、降本增效&#xff0c;越来越多的企业开始从传统的办公模式转向智慧办公。 以智能会议室为例&#xff0c;会议是企业业务中不可或缺的一部分&#xff0c;但在传统办公模式下&#xff0c;一来会议前行政人员需要提前准备会议材料…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站