背包问题分析代码详解【01背包+完全背包+多重背包】

这篇具有很好参考价值的文章主要介绍了背包问题分析代码详解【01背包+完全背包+多重背包】。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一、01背包问题

问题描述:

有 N 件物品和一个容量为 V 的背包,每件物品有各自的价值且只能被选择一次,要求在有限的背包容量下,装入的物品总价值最大。

朴素01背包
  1. 状态f[i , j]定义:在前i个物品中选,总体积不超过j的价值最大值
  2. 状态转移
    1)选第i个物品:f[i,j] = f[i-1,j]
    2)不选第i个物品:f[i,j] = f[i-1, j-v[i] ] +w[i]
    我们的决策是如何取到最大价值,因此以上两种情况取max( )
for(int i = 1; i <= n; i++) 
        for(int j = 0; j <= m; j++)
        {
            //  当前背包容量装不进第i个物品,则价值等于前i-1个物品
                f[i][j] = f[i - 1][j];
            // 能装,需进行决策是否选择第i个物品
            if(j>=v[i])    
                f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
        }           
01背包优化成一维

一维01背包就是将状态f[i,j] 优化到一维f[j] ,减低了内存的开销,使代码更简洁。

这种方法适合任何背包问题,在接下来的所有背包问题我们都是用一维的方法来分析。

1. 为什么可以这样变形呢?

​ 从朴素01背包问题来看,我们最终想要的答案是f[n,m] ,跟前n-1层无关,只是在计算的时候才会用到,但是用到的并不是所有的数据,我们通过状态转移可以发现我们当前层的转移只用到了上一层的数据,因此我们只需要保存上一层的数据,每次用上一层的数据计算即可。

2. 在二维变为一维的时候,有什么需要注意?

1) 在枚举背包容量的时候需要逆序

​ 因为在计算的我们是用较小的体积去更新较大的体积,所有我们每次在更新的时候,用到的是本层的状态,而不是上一层的状态。

2) 如何由二维优化到一维

我们只需要将前面一维删掉即可,具体变化如下:

      for(int i = 1; i <= n; i++) 
              for(int j = 1; j <= m; j++)
              {
                  //  当前背包容量装不进第i个物品,则价值等于前i-1个物品
                      f[i][j] = f[i - 1][j];  	//优化前
                      f[j] = f[j]      			//优化后
           
                  // 能装,需进行决策是否选择第i个物品
                  if(j>=v[i])    
                      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[j] = f[j] 是恒等式,无意义,所有我们去掉。

  • 我们将if(j>=v[i])放到循环条件里面。

这步为什么成立?变成一维之后,在j<v[i]的时候,由于我们用到的数据就是上一层的数据,所以我们不需要改变当前f的值。只有当j>=v[i]的时候,我们才拿上一层的值和放当前物品的价值取max即可。

简言之,在j<v[i]的时候,不需要动。在j>=v[i]的时候,令f[j] = max(f[j],f[j - v[i]]+w[i])

所以我们只需要从>=v[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]);
    }    

二、完全背包问题

问题描述:

有 N 件物品和一个容量为 V 的背包,每件物品有各自的价值可以被选择多次(0,1,2,3 … ),要求在有限的背包容量下,装入的物品总价值最大。

朴素完全背包
  1. 转态f[i,j]定义 :在前i个物品中选,总体积不超过j的最大价值。

  2. 状态转移方程

    f[i,j] = max(f[i-1,j],f[i-1,j-v[i]]+w[i],f[i-1,j-2v[i]]+2w[i]…f[i-1,j-sv[i]]+sw[i])
    s表示能取到的最大值,不超过体积即可

    分析:

    ​ 据题目要求,我们在考虑第i个物品的时候,我们可以不选,选1个,选2个。。。可以选到选不下为止。在这些所有转态中,我们找到一种最大情况。

代码

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] = max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);
优化一维的完全背包

1. 首先我们先来看如何优化掉内层循环

在上面朴素代码最内层的循环含义是找到放多个第i个物品可以可以使得当前体积获得的价值最大,数学关系式如下:

f[i , j ] = max( f[i-1,j] , f[i-1,j-v]+w , f[i-1,j-2v]+2w , f[i-1,j-3v]+3w , …)

f[i,j-v]如下:

f[i , j-v]= max( f[i-1,j-v] , f[i-1,j-2v] + w , f[i-1,j-3v]+2*w , …)

我们发现上面两个式子中,第一个式子的f[i-1,j-v]+w , f[i-1,j-2v]+2w , f[i-1,j-3v]+3w , … 可以用f[i,j-v]+w替换可得出如下递推关系: f[i,j]=max(f[i,j-v]+w , f[i-1,j])

优化一层循环后的代码:

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]>=0)
            f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i]);
    }

2. 01背包和完全背包的区别

​ 这个代码和01背包的代码十分相似,唯一区别就是,01背包进行状态计算的时候,每次用到的是上一层的状态,而完全背包是用本层已经更新的状态去更新。

f[i][j] = max(f[i][j],f[i-1][j-v[i]]+w[i]); //01背包

f[i][j] = max(f[i][j],f[i][j-v[i]]+w[i]); //完全背包问题

3. 一维完全背包的优化

​ 这个优化和01背包几乎一致,唯一的区别 在于内层循环的顺序。为什么? 参考上面

for(int i = 1 ; i<=n ;i++)
    for(int j = v[i] ; j<=m ;j++)//注意了,这里的j是从小到大枚举,和01背包不一样
     	f[j] = max(f[j],f[j-v[i]]+w[i]);

三、多重背包问题

问题描述:

有 N 件物品和一个容量为 V 的背包,每件物品有各自的价值可以被选择多次但最多只能选择S次,要求在有限的背包容量下,装入的物品总价值最大。

朴素多重背包
  1. 转态f[i,j]定义 :在前i个物品中选,总体积不超过j的最大价值。

  2. 状态转移方程
    f[i,j] = max(f[i-1,j],f[i-1,j-v[i]]+w[i],f[i-1,j-2v[i]]+2w[i]…f[i-1,j-v[i]]+sw[i])
    s表示能取到的最大值,其中 s<=S 并且 s*v[i] <= j 。

  3. 完全背包和多重背包的区别
    二者区别在于完全背包对于当前物品可以选无数个,直到背包装不下为止。而多重背包是对完全背白的选择进行了限制,每个物品只能选择S个。可以理解成有限制的完全背包问题

for(int i = 0;i<n;i++){
	for(int j = 0;j<=m;j++){
		for(int k = 0;k<=s[i] && k*v[i] <= j;k++){
			f[i][j] = max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);
		}
	}
}
多重背包的二进制优化

1. 能不能用完全背包优化方法来优化呢?

  • f[i , j ] = max( f[i-1,j] , f[i-1,j-v]+w , f[i-1,j-2v]+2w , f[i-1,j-3v]+3w , … f[i-1,j-sv]+sw)
  • f[i , j-v]= max( f[i-1,j-v] , f[i-1,j-2v] + w , f[i-1,j-3v]+2w , … f[i-1,j-sv]+(s-1)w , f[i-1,j-(s+1)v]+sw)

由于f[i,j-v]中多了一项f[i-1,j-(s+1)v]+sw,所以 f[i-1,j-v]+w , f[i-1,j-2v]+2w , f[i-1,j-3v]+3w , … f[i-1,j-sv]+sw 这一坨的最大值不能用f[i,j-v]+w表示,因此不能采用与完全背包同样的方法优化。

2. 二进制优化的思想以及为什么用这种方法?

1)有一个数13,我们把13分成1,2,4,6 这四个数,我们可以拿这四个数可以表示任意1~13的数。

2)在清楚上一步之后,我们用上述思想转换到本题。在正常背包的思路下,假设这一类物品有13个,我们要求出这一类物品的最大价值,需要考虑每一种情况,也就是枚举14次(0~13)。假设我们现在将这13个物品打包成1,2,4,6,把他们看成4个单独的物品,我们只需要考虑每件物品选与不选,就可以产生选0 ~ 13 其中的任意一种情况,而且只需要考虑4次。这就大大降低了我们枚举的次数。

3)我们将每一类物品进行打包之后,我们对于打包之后的每一个物品的选与不选,可以转化成01背包问题。

3. 最终实现代码

#include<bits/stdc++.h>
using namespace std;
const int N = 15000;
int n,m;
int logs[N],w[N];
int f[N];
int main()
{
	cin>>n>>m;
    int cnt = 0;
	for(int i = 0;i<n;i++){
		int a,b,s;  	//a体积,b表示价值 ,s表示该类物品的个数
        cin>>a>>b>>s;
        int t = 1;
        while(s >= t){  //将每一类物品按二进制数打包
            cnt++;
            logs[cnt] = t * a;
            w[cnt] = t * b;
            s -= t;
            t *= 2;
        }
        if(t > 0){     //不足,单独算一个
            cnt++;
            logs[cnt] = s * a;
            w[cnt] = s * b;
        }
        
    }
    for(int i = 1;i<=cnt;i++){
		for(int j = m;j>=logs[i];j--){
			f[j] = max(f[j],f[j-logs[i]]+w[i]);
        }
    }
    cout<<f[m]<<endl;
    return 0;
}
多重背包单调队列优化

1. f[i,j]当前最大价值是对于第i类物品,选择0~S个(S是该类物品的最大个数)这些情况下的价值的最大值

2. 根据上面的定义我们列出所有的情况。

 >f[i,j]=max(f[i-1,j],f[i-1,j-v]+w,f[i-1,j-2v]+2w,...,f[i-1,j-kv]+kw);
 >f[i,j-v]=max(        f[i-1,j-v],  f[i-1,j-2v]+w, ...,f[i-1,j-kv]+(k-1)w,f[i-1,j-(k+1)v]+kw);
 >...
 >f[i,r] = max(...)  r = j - 能取到的最大物品个数k * v ,也可以理解成j % v 的余数

3. 对体积0~m,我们可以分为v组,每组大小s,对于任何一个 j = v*s+ r,所以我们可以得到一个容量为s的滑动串窗口。对于体积为m,并在第i类物品的选择下的情况(即f[i,m])

 f(i,r)=f[i,r]
 
 f(i,r+v)=max(f[i,r+v]-w,f[i,r])
 
 f(i,r+2v)=max(f[i,r+2v]-2w,f[i,r+v]-w,f[i,r])
 
 ⋯
 
 f(i,r+(s−1)v)=max(f[i,r+(s-1)v],f[i,r+(s - 2)v]+w,⋯,f[i,r]+(s−1)w)
 
 f(i,r+sv)=max(f[i,r+sv],f[i,r+(s-1)v]+w,⋯,f[i,r]+sw)               (滑动窗口已满)
 
 f(i,r+(s+1)v)=max(f[i,r+(s+1)v],f[i,r+sv]+w,⋯,f[i,r+v]+sw)    (滑动窗口已满)

⋯
 
 f(i,j−2v)=max(f[i,j−2v],f[i,j−3v]+w,⋯,f[i,j−(s+2)v]+sw)          (滑动窗口已满)
 
 f(i,j−v)=max(f[i,j−v],f[i,j−2v]+w,⋯,f[i,j−(s+1)v]+sw)              (滑动窗口已满)
 
 f(i,j)=max(f[i,j],f[i,j−v]+w,⋯,f[i, j−sv]+sw)                                (滑动窗口已满)

4. 根据上面我们可以用一个单调队列来维护我们需要用到的体积

  • 当超过我们容量s的时候,队头弹出一个元素
  • 当要插入的体积对应的最大值大于等于队尾的最大值,要弹出队尾,直到满足为止
  • 插入当前体积

5. 每次入队的值是 dp[j-kv] + kw计算w的倍数,可以通过队列存的体积与当前枚举的体积之差模上v而得。

具体代码如下:文章来源地址https://www.toymoban.com/news/detail-463589.html

#include<bits/stdc++.h>
using namespace std;

const int N = 1010,M = 20010;  
int n,m;
int v[N],w[N],s[N];  //体积 价值 数量
int f[M],g[M];   	 //dp数组和备份数组
int q[M];   		 //维护滑动窗口的单调队列
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++){
        memcpy(g,f,sizeof f);
        for(int j = 0;j<v[i];j++){    //分成v[i]组
            int hh = 0,tt = -1;
            for(int k = j;k<=m;k += v[i]){
                while (hh <= tt && k - q[hh] > s[i] * v[i]) hh ++ ;
                while (hh <= tt && g[q[tt]] + (k - q[tt])/v[i] * w[i] <= g[k]) tt--;
                q[ ++ tt] = k;
                f[k] = g[q[hh]] + (k - q[hh]) / v[i] * w[i];
            }
        }
    }
    cout<<f[m]<<endl;
    return 0;
    
}

到了这里,关于背包问题分析代码详解【01背包+完全背包+多重背包】的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 代码随想录 Day35 动态规划04 01背包问题和完全背包问题 LeetCode T416 分割等和子集

    说到背包问题大家都会想到使用动规的方式来求解,那么为什么用动规呢, dp数组代表什么呢 ? 初始化是什么 , 遍历方式又是什么 ,这篇文章笔者将详细讲解背包问题的经典例题0-1背包问题和完全背包问题的解题方式,希望能帮助到大家 有人一提到背包问题就只会使用动态规划来

    2024年02月06日
    浏览(75)
  • 【算法日志】动态规划刷题:01背包问题,多重背包问题(day37,day38)

    目录 前言 目标和(01背包) 一和零(01背包) 零钱兑换(多重背包) 排列总和(多重背包) 这两天都是背包问题,其中的01背包的一些应用问题需要一定的数学建模能力,需要i将实际问题简化成我们熟悉的背包问题;而这两天的多重背包问题还算比较基础,但也要我明白了

    2024年02月11日
    浏览(56)
  • 背包问题——01背包|完全背包

    目录 前言背包问题的历史  01背包  1、题目 2、暴力解01背包  Ⅰ、代码 3、动态规划解01背包 Ⅰ、二维dp数组解01背包 1)dp数组的含义  2)递推公式  3)dp数组的初始化  4)遍历顺序的讨论  5、代码  Ⅱ、一维数组解01背包  1)一维数组|滚动数组  2)一维数组的含义及递

    2024年02月02日
    浏览(47)
  • 关于完全背包的解析以及完全背包与01背包的区别及代码

    完全背包是什么呢?如果大家了解过01背包那么完全背包也是可以理解的。完全背包也是求一个固定容量的背包,能够装入物品的最大价值是多少,也就是说该背包最多能装多少价值?和01背包不同的是,完全背包里所能装的各个物品给定是无限的,也就是说同一个物品我们可

    2023年04月09日
    浏览(34)
  • 算法套路十四——动态规划之背包问题:01背包、完全背包及各种变形

    如果对递归、记忆化搜索及动态规划的概念与关系不太理解,可以前往阅读算法套路十三——动态规划DP入门 背包DP介绍:https://oi-wiki.org/dp/knapsack/ 0-1背包:有n个物品,第i个物品的体积为w[i],价值为v[i],每个物品至多选一个, 求体积和不超过capacity时的最大价值和,其中i从

    2024年02月10日
    浏览(59)
  • 多重背包问题(详解二进制优化原理)

    这道题同样是背包问题,那么它也同样满足三个性质:重叠子问题、最优子结构以及无后效性。那么这样的话,我们依然可以使用动态规划的思路去分析这道题目。那么动态规划的分析主要分为两步:状态转移方程的书写以及循环的设计。 (1)状态表示: 我们在前面的两篇

    2024年02月14日
    浏览(38)
  • 动态规划-----背包类问题(0-1背包与完全背包)详解

    目录 什么是背包问题? 动态规划问题的一般解决办法: 0-1背包问题: 0 - 1背包类问题  分割等和子集:  完全背包问题:  完全背包类问题 零钱兑换II: 背包问题(Knapsack problem)是一种组合优化的NP完全问题。 问题可以描述为:给定一组物品,每种物品都有自己的重量和价格

    2024年04月17日
    浏览(35)
  • 动态规划:0-1背包、完全背包问题 | 详细原理解释 | 代码及优化(C++)

    目录 01背包 问题描述: 简单描述就是: 解析: 递推公式: dp数组的初始化: 遍历顺序: 图解: 实现代码: dp数组初始化: 遍历: 优化: 原理: 递推公式: 遍历顺序: 实现代码: 初始化: 遍历: 完全背包 问题描述: 解析: 实现代码:         01背包是在M件物品

    2024年02月11日
    浏览(36)
  • 算法 DAY45 动态规划07 70. 爬楼梯 322. 零钱兑换 279. 完全平方数 139. 单词拆分 多重背包

    和377. 组合总和 Ⅳ (opens new window)基本就是一道题了。 本题代码不长,题目也很普通,但稍稍一进阶就可以考察完全背包 动态规划五部曲 1、确定dp[j]的含义 dp[j] 凑成 j 的最少硬币的个数 2、确定递推公式 比如想凑成3, 如果手里有1,那么最小个数就是dp[2]+1 如果手里有2,那

    2024年02月02日
    浏览(60)
  • 【LeetCode动态规划#08】完全背包问题实战与分析(零钱兑换II)

    力扣题目链接(opens new window) 给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。 示例 1: 输入: amount = 5, coins = [1, 2, 5] 输出: 4 解释: 有四种方式可以凑成总金额: 5=5 5=2+2+1 5=2+1+1+1 5=1+1+1+1+1 示例 2: 输入: amount = 3

    2023年04月19日
    浏览(46)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包