【动态规划】背包问题(01背包,完全背包)

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

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


🌈个人主页:主页链接


🌈算法专栏:专栏链接


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


🌈LeetCode专栏:专栏链接


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


🌈代码仓库:Gitee链接


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


好**难啊,整抑郁了


DP:


DP有这样的一个分析方法

52014167dd87461db06aa828718b5c98.jpg


题目:01背包问题


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


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


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

输出最大价值。


输入格式


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


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


输出格式


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


数据范围


0<N,V≤1000

0<vi,wi≤1000


输入样例


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


dbe73ed2a435496e932da2349d06aadb.jpg


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


代码实现:


#include<iostream>
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的容积下价值都为0
   for (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的容积下价值都为0
    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];
}


但观察此时的状态方程.


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的容积下价值都为0
    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];
}


题目:完全背包


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


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


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

输出最大价值。


输入格式


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


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


输出格式


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


数据范围


0<N,V≤1000

0<vi,wi≤1000


输入样例


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

1ca038be141f44a790e0f446aef26821.jpg


代码实现:


#include <algorithm>
#include<iostream>
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的容积下价值都为0
    for(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<<f[n][m];
}


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



优化:


95709dbc9dfa4bfaa07d52d5bc9a6637.jpg


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


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


代码实现:


#include <algorithm>
#include<iostream>
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的容积下价值都为0
    for(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<<f[n][m];
}


优化


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


代码实现:


#include <algorithm>
#include<iostream>
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的容积下价值都为0
    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]);//表示已经选入第i层 
        }
    }
    cout<<f[m];
}


完结撒花:


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

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


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


🌈诸君,山顶见!

ppeua
+关注
目录
打赏
0
0
0
0
10
分享
相关文章
突破极限: 高负载场景下的单机300M多行正则日志采集不是梦
在当今数字化时代,日志数据已成为企业 IT 运营和业务分析的关键资源。然而,随着业务规模的扩大和系统复杂度的提升,日志数据的体量呈现爆发式增长,给日志采集和处理系统带来了巨大挑战。
403 99
程序员必知:动态规划——背包问题1:01背包
程序员必知:动态规划——背包问题1:01背包
78 0
动态规划之01背包问题和完全背包问题
动态规划之01背包问题和完全背包问题
【背包问题】01背包问题和完全背包问题的模板
【背包问题】01背包问题和完全背包问题的模板
115 1
外汇MT5/MT4交易所平台系统开发测试版/案例设计/策略步骤/功能需求/源码程序
When developing the MT5/MT4 foreign exchange documentary trading system, the following functions and intelligence can also be considered:
动态规划之背包问题——背包三讲(01背包,完全背包,多重背包)(三)
动态规划之背包问题——背包三讲(01背包,完全背包,多重背包)(三)
291 0
动态规划之背包问题——背包三讲(01背包,完全背包,多重背包)(三)
背包问题——01背包|完全背包 1
背包问题——01背包|完全背包
464 0
背包问题——01背包|完全背包 2
背包问题——01背包|完全背包
290 0
AI助理
登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问

你好,我是AI助理

可以解答问题、推荐解决方案等