【动态规划】背包问题(01背包,完全背包)
创始人
2024-05-31 04:44:30
0

Halo,这里是Ppeua。平时主要更新C语言,C++,数据结构算法......感兴趣就关注我吧!你定不会失望。

🌈个人主页:主页链接

🌈算法专栏:专栏链接

     我会一直往里填充内容哒!

🌈LeetCode专栏:专栏链接 

    目前在刷初级算法的LeetBook 。若每日一题当中有力所能及的题目,也会当天做完发出

🌈代码仓库:Gitee链接

🌈点击关注=收获更多优质内容🌈

目录

DP:

题目:01背包问题

题解:

代码实现:

优化:

代码实现:

题目:完全背包

题解:

代码实现:

优化: 

代码实现:

优化 

代码实现:

完结撒花:


 

好**难啊,整抑郁了 

DP:

DP有这样的一个分析方法

题目:01背包问题

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。

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

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

输入格式

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

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

输出格式

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

数据范围

0 0

输入样例

4 5
1 2
2 4
3 4
4 5

输出样例:

8

题解:

分析01背包问题的特点:有N件物品,背包容积是V,每件物品只能拿(0)或不拿(1),所以称为01背包问题.

将问题分析,当决定第i件拿与不拿的时候,表达式为:此时背包价值=max(背包没拿第i件物品的价值,拿了第i件物品的价值)

所以这里的状态表示的集合为:从前i件物品拿,且总体积不超过j

                   状态表示的属性为:最大值

        状态计算为f[i][j],其中i为第几件物品,j为此时背包的容量

其中不选第i件物品总价值,就为前一个相同容量的背包中的价值

        因为直接计算选第i件物品比较难计算,所以我们将选第i件物品的价值转换为,不选第i件物品的价值,并令其背包容积减去第i件物品的v再加上其价值w

所以我们的状态方程就为:f[i][j]=max(f[i-1],f[i-1][j-v]+w) 

代码实现:

#include
using namespace std;
int n, m;
const int N = 1010;
int v[N], w[N];
int f[N][N];
int solution1()
{cin >> n >> m;for (int i = 1; i <= n; i++)cin >> v[i] >> w[i];for (int i = 0; i <= m; i++)f[0][i] = 0;//一件物品都没选 0-m的容积下价值都为0for (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 - 1][j - v[i]] + w[i]);//在拿i-1件物品,其容量为j-vi时放入物品的最大值 }}cout << f[n][m];
} 

优化:

观察.f[i][j]的变换形式,每次计算只用到了上一层i,j,所以我们可以将i这一维给删了,变成这种形式

直接将[i]删了

int n, m;
const int N = 1010;
int v[N], w[N];
int f[N];
int main()
{cin >> n >> m;for (int i = 1; i <= n; i++)cin >> v[i] >> w[i];for (int i = 0; i <= m; i++)f[i] = 0;//一件物品都没选 0-m的容积下价值都为0for (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];
}

但观察此时的状态方程.

f[j-v[i]]+w[i],用到的是这一层已经计算的数据(因为j是从小开始算的,也就是说从小的j开始就会把上一次计算的j给覆盖了,而后面要用到的是上面一层i-1的数据,而不是i)

所以我们为了避免这种情况,使用i-1的数据,我们从后往前遍历,这样每一次计算j时,用的就是i-1层的数据,与上文所述一致 

代码实现:

int n, m;
const int N = 1010;
int v[N], w[N];
int f[N];
int main()
{cin >> n >> m;for (int i = 1; i <= n; i++)cin >> v[i] >> w[i];for (int i = 0; i <= m; i++)f[i] = 0;//一件物品都没选 0-m的容积下价值都为0for (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];
}

题目:完全背包

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

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

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

输入格式

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

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

输出格式

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

数据范围

0 0

输入样例

4 5
1 2
2 4
3 4
4 5

输出样例:

10

题解:

完全背包问题是01背包问题的升级版.每件物品不再只能拿一件,而可以无限拿(在容量允许的情况下)

将问题分析,当决定第i件拿K件,表达式为:此时背包价值=max(背包没拿第i件物品的价值,拿了K*第i件物品的价值)

所以这里的状态表示的集合为:从前i件物品拿K件,且总体积不超过j

                   状态表示的属性为:最大值

        状态计算为f[i][j],其中i为第几件物品,j为此时背包的容量

其中不选第i件物品总价值,就为前一个相同容量的背包中的价值

        因为直接计算拿第i件k个比较难计算,所以我们将选第i件物品的价值转换为,不选第i件物品的价值,并令其背包容积减去第i件物品的K*v再加上其价值K*w

 

代码实现:

#include 
#include
using namespace std;
int n, m;
const int N = 1010;
int v[N], w[N];
int f[N][N];
int main()
{for (int i = 1; i <= n; i++)cin >> v[i] >> w[i];for (int i = 0; i <= m; i++)f[0][i] = 0;//一件物品都没选 0-m的容积下价值都为0for(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]=f[i-1][j];if(j>=k*v[i])f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);}}}cout<

这和01背包问题的朴素做法几乎一模一样,但这里的时间复杂度为n^3,所以我们得优化一下,不然就TLE了  

 

优化: 

 

 对于f[i,j-v]的含义是:将J>=K*V时,我们先将第i个物品放入背包,之后再去找当前容量下能放入的最大价值的东西,之后再加上w,这时候就可以不用考虑具体放几件了,

最后也就变成了f[i][j]=Max(f[i-1][j],f[i][j-v]+w)

代码实现:

#include 
#include
using namespace std;
int n, m;
const int N = 1010;
int 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];for (int i = 0; i <= m; i++)f[0][i] = 0;//一件物品都没选 0-m的容积下价值都为0for(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]);//表示已经选入第i层 }}cout<

优化 

因为还是N^2,观察这个表达式,和01背包问题很想,且也只用到了i-1层 所以可以用滚动数组优化,删掉一维即可,因为这里计算max的时候用的式i 所以不用进行从大到小的处理

代码实现:

#include 
#include
using namespace std;
int n, m;
const int N = 1010;
int v[N], w[N];
int f[N];
int main()
{cin>>n>>m;for (int i = 1; i <= n; i++)cin >> v[i] >> w[i];for (int i = 0; i <= m; i++)f[i] = 0;//一件物品都没选 0-m的容积下价值都为0for(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]);//表示已经选入第i层 }}cout<

完结撒花:

🌈本篇博客的内容【动态规划 :背包问题(01背包,完全背包)】已经结束。

🌈若对你有些许帮助,可以点赞、关注、评论支持下博主,你的支持将是我前进路上最大的动力。

🌈若以上内容有任何问题,欢迎在评论区指出。若对以上内容有任何不解,都可私信评论询问。

🌈诸君,山顶见!

相关内容

热门资讯

安卓10系统省电不,安卓10系... 你有没有发现,自从升级到安卓10系统,手机续航能力好像大不如前了?别急,今天就来给你揭秘安卓10系统...
cm14安卓系统,深度定制与极... 你有没有发现,你的安卓手机最近是不是有点不一样了?是不是觉得系统运行得更加流畅,界面也更加美观了呢?...
平板安卓系统咋样升级,轻松实现... 你那平板安卓系统是不是有点儿卡,想给它来个升级大变身?别急,让我来给你详细说说平板安卓系统咋样升级,...
安卓原系统在哪下载,探索纯净体... 你有没有想过,为什么安卓手机那么受欢迎?那是因为它的系统——安卓原系统,它就像是一个充满活力的魔法师...
安卓系统procreate绘图... 你有没有发现,现在手机上画画变得越来越流行了?尤其是用安卓系统的手机,搭配上那个神奇的Procrea...
电视的安卓系统吗,探索安卓电视... 你有没有想过,家里的电视是不是也在悄悄地使用安卓系统呢?没错,就是那个我们手机上常用的安卓系统。今天...
苹果手机系统操作安卓,苹果iO... 你有没有发现,身边的朋友换手机的时候,总是对苹果和安卓两大阵营争论不休?今天,咱们就来聊聊这个话题,...
安卓系统换成苹果键盘,键盘切换... 你知道吗?最近我在想,要是把安卓系统的手机换成苹果的键盘,那会是怎样的体验呢?想象那是不是就像是在安...
小米操作系统跟安卓系统,深度解... 亲爱的读者们,你是否曾在手机上看到过“小米操作系统”和“安卓系统”这两个词,然后好奇它们之间有什么区...
miui算是安卓系统吗,深度定... 亲爱的读者,你是否曾在手机上看到过“MIUI”这个词,然后好奇地问自己:“这玩意儿是安卓系统吗?”今...
安卓系统开机启动应用,打造个性... 你有没有发现,每次打开安卓手机,那些应用就像小精灵一样,迫不及待地跳出来和你打招呼?没错,这就是安卓...
小米搭载安卓11系统,畅享智能... 你知道吗?最近小米的新机子可是火得一塌糊涂,而且听说它搭载了安卓11系统,这可真是让人眼前一亮呢!想...
安卓2.35系统软件,功能升级... 你知道吗?最近在安卓系统界,有个小家伙引起了不小的关注,它就是安卓2.35系统软件。这可不是什么新玩...
安卓系统设置来电拦截,轻松实现... 手机里总是突然响起那些不期而至的来电,有时候真是让人头疼不已。是不是你也想摆脱这种烦恼,让自己的手机...
专刷安卓手机系统,安卓手机系统... 你有没有想过,你的安卓手机系统是不是已经有点儿“老态龙钟”了呢?别急,别急,今天就来给你揭秘如何让你...
安卓系统照片储存位置,照片存储... 手机里的照片可是我们珍贵的回忆啊!但是,你知道吗?这些照片在安卓系统里藏得可深了呢!今天,就让我带你...
华为鸿蒙系统不如安卓,挑战安卓... 你有没有发现,最近手机圈里又掀起了一股热议?没错,就是华为鸿蒙系统和安卓系统的较量。很多人都在问,华...
安卓系统陌生电话群发,揭秘安卓... 你有没有遇到过这种情况?手机里突然冒出好多陌生的电话号码,而且还是一个接一个地打过来,简直让人摸不着...
ios 系统 安卓系统对比度,... 你有没有发现,手机的世界里,iOS系统和安卓系统就像是一对双胞胎,长得差不多,但细节上却各有各的特色...
安卓只恢复系统应用,重拾系统流... 你有没有遇到过这种情况?手机突然卡顿,或者某个应用突然罢工,你一气之下,直接开启了“恢复出厂设置”大...