01背包问题c++
创始人
2025-05-29 18:04:25
0

问题

问题介绍

有 N 种物品和一个容量是 V 的背包,每种物品都有无限件可用。

第 i 种物品的体积是 vi,价值是 wi。

求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。
输出最大价值。

输入格式

第一行两个整数,N,V,用空格隔开,分别表示物品种数和背包容积。

接下来有 N 行,每行两个整数 vi,wi,用空格隔开,分别表示第 i 种物品的体积和价值。

输出格式

输出一个整数,表示最大价值。

讲解

首先要说明的就是,本教程只讲解一般的写法,不讲解优化方法(滚动数组降维),先把基本的思想学会了,然后再去学优化方法的。
相信大多数人刚开始学dp问题的时候碰到的就是01背包问题,dp问题首先就是先定义dp数组所代表的意义(比如说这道题,dp[i][j]所代表的就是选取前i个物品体积不会超过j的最大价值),然后就是判断每一步的状态(比如说这一题就是每一步都要判断是否选择这个物品),然后就是状态转移方程了。
回归本题目,本题的思想就是装前i个物品,然后体积一直增大,每次就是判断选不选这个物品,

  • 如果选这个物品的价值就是dp[i - 1][j - v[i]] + w[i]
    解析:选这一个那么肯定要加上这一个的价值w[i]这里应该没有问题了吧,那为什么前面是dp[i - 1][j - v[i]]呢?因为就是选了这一个物品了,这一个物品占据了v[i]的体积,那么只要找到子问题选i-1个物品,然后体积不大于j-v[i]的最优解就可以了。
  • 如果不选这个物品,就直接从前i-1个物品选体积不大于j的最优解了。
  • 每次判断一下,就是如果这个物品的体积大于现在所能装的最大的体积,那么肯定就是直接不能选择这个物品了。

图解

  • 图片中在中间价值数据中被标黄的数据就是当前物品的体积大于背包当前所能装的最大体积,所以直接就不用选这个物品,直接将上一层的数据拉下来就行了。
  • 图片可能会不好看哈,等我优化。
    01背包.png

基础源码

#include using namespace std;const int N = 1010;int n, k;
int v[N], m[N];
int dp[N][N];int main()
{cin >> n >> k;for (int i = 1; i <= n; i ++ ) cin >> v[i] >>m[i];for (int i = 1; i <= n; i ++ ){for (int j = 1; j <= k; j ++ ){if (v[i] > j){dp[i][j] = dp[i - 1][j];}else{dp[i][j] = max(dp[i - 1][j - v[i]] + m[i], dp[i - 1][j]);}}}cout << dp[n][k] << endl;}

一维数组优化

  • 来自几个小时后的我:看了一下y总的视频,突然就会了一维数组的优化方法是怎么写的了。
  • 其实如果上面那个图你从头推了一遍,你就会发现我们更新每一层的数据的时候,其实只用到了上一层的数据而且还是用到上一层数据的范围为–>从上一层起点开始到本层数据正上方的数据。比如说我们要更新第三层第4列的数据,那么其实我们用到的数据范围为,第3-1层第一列到第3-1层第4列。
  • 我们遍历j的时候要从后(最大的体积)向前遍历到v[i]
    • 为什么要从后开始遍历呢?
      因为我们每次更新要用到前面的数据,如果我们从前向后更新,当我们遍历到后边的时候要用到前面的数据但是前面的数据已经更改了,不是第i-1层的数据了,所以我们要从后向前遍历,这样就不会影响到前面的数据。
    • 为什么遍历到v[i]就可以了呢?
      因为就是j的时候肯定是不能选这个物品的,直接就是拉取正上方的数据就行,也就相当于不用更改数据。

一维数组优化后源码

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

相关内容

热门资讯

安卓系统换成苹果键盘,键盘切换... 你知道吗?最近我在想,要是把安卓系统的手机换成苹果的键盘,那会是怎样的体验呢?想象那是不是就像是在安...
小米操作系统跟安卓系统,深度解... 亲爱的读者们,你是否曾在手机上看到过“小米操作系统”和“安卓系统”这两个词,然后好奇它们之间有什么区...
miui算是安卓系统吗,深度定... 亲爱的读者,你是否曾在手机上看到过“MIUI”这个词,然后好奇地问自己:“这玩意儿是安卓系统吗?”今...
安卓系统开机启动应用,打造个性... 你有没有发现,每次打开安卓手机,那些应用就像小精灵一样,迫不及待地跳出来和你打招呼?没错,这就是安卓...
小米搭载安卓11系统,畅享智能... 你知道吗?最近小米的新机子可是火得一塌糊涂,而且听说它搭载了安卓11系统,这可真是让人眼前一亮呢!想...
安卓2.35系统软件,功能升级... 你知道吗?最近在安卓系统界,有个小家伙引起了不小的关注,它就是安卓2.35系统软件。这可不是什么新玩...
安卓系统设置来电拦截,轻松实现... 手机里总是突然响起那些不期而至的来电,有时候真是让人头疼不已。是不是你也想摆脱这种烦恼,让自己的手机...
专刷安卓手机系统,安卓手机系统... 你有没有想过,你的安卓手机系统是不是已经有点儿“老态龙钟”了呢?别急,别急,今天就来给你揭秘如何让你...
安卓系统照片储存位置,照片存储... 手机里的照片可是我们珍贵的回忆啊!但是,你知道吗?这些照片在安卓系统里藏得可深了呢!今天,就让我带你...
华为鸿蒙系统不如安卓,挑战安卓... 你有没有发现,最近手机圈里又掀起了一股热议?没错,就是华为鸿蒙系统和安卓系统的较量。很多人都在问,华...
安卓系统陌生电话群发,揭秘安卓... 你有没有遇到过这种情况?手机里突然冒出好多陌生的电话号码,而且还是一个接一个地打过来,简直让人摸不着...
ios 系统 安卓系统对比度,... 你有没有发现,手机的世界里,iOS系统和安卓系统就像是一对双胞胎,长得差不多,但细节上却各有各的特色...
安卓只恢复系统应用,重拾系统流... 你有没有遇到过这种情况?手机突然卡顿,或者某个应用突然罢工,你一气之下,直接开启了“恢复出厂设置”大...
安卓系统出现支付漏洞,揭秘潜在... 你知道吗?最近安卓系统可是闹出了不小的风波呢!没错,就是那个我们每天离不开的安卓系统,竟然出现了支付...
苹果换了安卓系统恢复,体验变革... 你有没有遇到过这种情况?手机里的苹果突然变成了安卓系统,而且还是那种让你摸不着头脑的恢复模式。别急,...
安卓怎么卸载系统app,轻松告... 手机里的系统应用越来越多,有时候真的让人眼花缭乱。有些应用虽然看起来很实用,但用起来却发现并不适合自...
安卓系统查看步数,揭秘日常运动... 你有没有发现,每天手机里的小秘密越来越多?今天,咱们就来聊聊安卓系统里那个悄悄记录你每一步的小家伙—...
安卓系统未来会不会,未知。 你有没有想过,那个陪伴我们手机生活的安卓系统,它的未来会怎样呢?想象每天早上醒来,手机屏幕上跳出的信...
安卓系统怎么设置截图,轻松捕捉... 亲爱的手机控们,你是不是也和我一样,有时候想记录下手机屏幕上的精彩瞬间呢?别急,今天就来手把手教你如...
安卓系统下载软件安装,安卓系统... 你有没有发现,手机里的安卓系统就像一个巨大的宝藏库,里面藏着各种各样的软件,让人眼花缭乱。今天,就让...