完全背包 订阅
完全背包,是一种经典的信息学问题,是研究一个固定容量的背包内能装多大价值的东西的问题。 展开全文
完全背包,是一种经典的信息学问题,是研究一个固定容量的背包内能装多大价值的东西的问题。
信息
属    于
一种经典的信息学问题
概    念
研究固定容量背包能装多大价值
类似于
01背包问题
中文名
完全背包
完全背包完全背包问题
题目有N种物品和一个容量为V的背包,每种物品都有无限件可用。第i种物品的体积是c,价值是w。求解将哪些物品装入背包可使这些物品的体积总和不超过背包容量,且价值总和最大。
收起全文
精华内容
下载资源
问答
  • 动态规划之完全背包问题。 完全背包是在N种物品中选取若干件(同一种物品可多次选取)放在空间为V的背包里,每种物品的体积为C1,C2,…,Cn,与之相对应的价值为W1,W2,…,Wn.求解怎么装物品可使背包里物品总价值...
  • 背包问题九讲中的完全背包问题的三种算法的具体java实现代码。
  • 完全背包问题N件物品放入容量为C的背包。第i件物品的费用(重量、体积等)为wi,价值为vi。每件物品可以取用任意多次(无限数量),选择将哪些物品放入背包令总费用不超过背包的容量且物品的价值总和最大。输入格式...
  • 详细的完全背包问题1的C语言代码
  • 完全背包问题

    2018-09-16 07:18:24
    教学课件,可以用于信息学奥赛的课程培训课件,内容非常完整!
  • 完全背包算法代码.cpp

    2020-03-26 10:14:34
    大家好,这是我自己精简出的代码,大家可以尽情下载,同时,也可以看看我关于这算法的文章,谢谢。请大家多多支持我哦
  • 背包问题(0-1背包,完全背包,多重背包知识概念详解)内含实例代码解析,详细讲解了背包的基本概念及简单运用问题
  • 01背包问题:  先来看一个二维dp数组的写法,具体解释看注释即可: def bag_01_2D(): weight = [1, 3, 4] value = [15, 20, 30] bag_weight = 4 #状态定义:dp[i][j]表示从0-i 个 物品中选择不超过j重量的物品...

    在这里插入图片描述

    学习之前建议收听音乐:你的背包🎒~

    ⭐🚂⭐背包问题一般模板:

    【注:这个一般性模板作为一个总结的东西,先把后面背包问题理解了再来看就清晰很多。当然有时候模版公式要根据实际问题修改】

    1️⃣内外循环分类:

    类型模板
    01背包问题外循环nums,内循环target,target倒序且target>=nums[i]; 【注:01背包内外循环不能颠倒(不过用二维的dp数组的话倒是可以逆序和颠倒)】
    01背包组合问题外循环nums,内循环target,target倒序且target>=nums[i];【注:01背包内外循环不能颠倒】
    纯完全背包问题外循环nums,内循环target,target正序且target>=nums[i];【注:完全背包内外循环可以颠倒,for循环做点小修改即可。公式不变(用二维的dp数组的话正序。也可以颠倒)】
    完全背包组合问题外循环nums,内循环target,target正序且target>=nums[i];【注:完全背包组合问题内外循环不能颠倒】
    完全背包排列问题外循环target,内循环nums,target正序且target>=nums[i];【注:完全背包排列问题内外循环不能颠倒】

    2️⃣问题分类:

    类型模板
    最值问题dp[j] = max/min(dp[j], dp[j-nums[i]]+1) 或 dp[j] = max/min(dp[j], dp[j-nums[i]]+nums[i]);
    存在问题dp[j] = dp[j] or dp[j-nums[i]];
    组合 or 排列问题dp[j] += dp[j-nums[i]]


    ⭐以下关于各背包问题的具体解释都在代码注释中。

    难度
    一、01背包问题
    二、完全背包问题
    三、多重背包问题
    四、01背包存在问题
    五、完全背包存在问题
    六、01背包组合问题
    七、完全背包组合问题
    八、完全背包排列问题

    🚀一、01背包问题:

     01背包可以说是其他背包问题的基础,一定要弄透彻!
    在这里插入图片描述
     先来看一个二维dp数组的写法,具体解释看注释即可:
    【注:下面是先遍历物品再遍历背包,这样会好理解点。当然先遍历背包,再遍历物品,也是可以的!因为从这两种情况的状态转移公式可以看出(两种情况状态转移公式是一样的,调换下for循环顺序而已),更新的数据都是来自正左和正上方向。当然在一些背包问题里,两个for循环的先后循序是非常常有讲究的】

    def bag_01_2D():
        weight = [1, 3, 4]
        value = [15, 20, 30]
        bag_weight = 4
    
        #状态定义:dp[i][j]表示从0-i 个 物品中选择不超过j重量的物品的最大价值
        #注意python中二维数组的创建方式
        dp = [[0]*(bag_weight+1) for _ in range(len(weight)+1)]
    
        #边界:
        # 第一列都是0,因为价值为0(因为初始化全部为0了这里就不用了),
        # 第一行表示只选取0号物品最大价值(要满足背包容量放⾜够放编号0物品)
        for j in range(bag_weight, weight[0]-1, -1):
            dp[0][j] = dp[0][j - weight[0]]+value[0]
    
        #外循环遍历物品
        for i in range(1, len(weight)):
            #内循环遍历背包容量
            for j in range(0, bag_weight+1):
                # 背包容量放不下第i个物品
                if j < weight[i]:
                    dp[i][j] = dp[i-1][j]
    
                # 背包容量放的下第i个物品,可放可不放
                # 不放:那就等于前i-1个物品(在容量j中)的最大价值
                # 放:那就等于前i-1个物品(在容量j-weight[i]中)的最大价值
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]]+value[i])
    
        return dp[len(weight)-1][bag_weight]
    

     因为从状态转移方程可以清晰看到 i 时刻只与上一时刻 i-1 相关。所以可以用一维数组取代二维数组进行滚动即可。后面其他两个背包问题都用一维数组,毕竟空间复杂度小。
     关于内循环逆序的例子解释(因为这样避免了正序时,前面的状态选了i物品,后面状态又基于它又选了i物品,而i物品只能选一次。所以逆序遍历可以保证只取一次物品):

    在这里插入图片描述

    def bag_01():
        weight = [1, 3, 4]
        value = [15, 20, 30]
        bag_weight = 4
    
        # dp[j]表示容量为j的背包能放下东西的最大价值
        dp = [0]*(bag_weight+1)
    
        # 外循环遍历物品
        for i in range(0, len(weight)):
            # 内循环遍历背包容量,一定要逆序!!!这样可以保证物品i只被放入一次
            # 从二维那个公式中我们可以知道,当前时刻i只和i-1时刻的状态有关,
            # 如果正序的话那,在一维中更新当前时刻i的dp[j]时,dp[j-weight[i]]变成了当前的时刻i的更新的,而此时需要的是上一时刻i-1的dp[j-weight[i]]的旧值(得益于逆序遍历,后面的先更新)
            # 所以逆序可以避免dp[j-weight[i]]的旧值被更新先。
            for j in range(bag_weight, weight[i]-1, -1):
                #上面二维的做法中的:if j < weight[i]和else在这里合为了下面一句话,因为满足if时相当于等于i-1时刻的状态,在这里不变还是d[j]即i-1时的状态,所以可以不写。
                #不放或放第i个物品
                #不放:则是取前i-1个物品时(在容量为j中)的最大价值
                #放:则是取前i-1个物品(在容量j-weight[i]中)的最大价值
                dp[j] = max(dp[j], dp[j-weight[i]]+value[i])
    
        return dp[bag_weight]
    

     那么上面的两个内外for循环能否调换位置呢?(即先遍历背包容量再遍历物品?)
     答:肯定不能啦,因为背包容量的遍历是逆序的(这样d[j]的前面小于j的索引都是0啊,都还是初始化的状态)。看状态转移公式可以知道,这样一来,后果就是每个背包只放了一个物品哈哈哈。

     而二维不用逆序是因为:
     因为对于二维dp,dp[i][j]都是通过上⼀层即dp[i - 1][j]计算而来(因为i-1时并没有取i物品,之所以逆序就是避免当前层重复取了 i 物品),本层的dp[i][j]并不会被覆盖!

    🚀二、完全背包问题:

    在这里插入图片描述
     就是将01背包中的内循环改成正序遍历,即可实现每种物品可以选无限次。(至于为什么正序,弄懂了前面01背包的逆序讲解这个就很好懂了):

    # 状态定义:dp[i][j]表示从0-i 种 物品中选择不超过j重量的物品的最大价值
    
    # 01背包中,状态转移为:max(dp[i-1][j], dp[i-1][j-weight[i]]+value[i])
    # 而完全背包中,状态转移为:max(dp[i-1][j], dp[i][j-weight[i]]+value[i]),具体解释看下面
    
    
    def bag_full():
        weight = [1, 3, 4]
        value = [15, 20, 30]
        bag_weight = 4
    
        # dp[j]表示容量为j的背包能放下物品的最大价值
        dp = [0]*(bag_weight+1)
    
        # 外循环遍历物品种类
        for i in range(0, len(weight)):
            #内循环遍历背包容量,正序,因为可以重复放
            for j in range(weight[i], bag_weight+1):
    
                # 背包容量放的下第i 种 物品,可放可不放
                # 不放:那就等于前i-1 种 物品(在容量j中)的最大价值
                # 放:那就等于前i 种 物品(在容量j-weight[i]中)的最大价值。
                # 选择放的时候,不取决与前一时刻的状态,因为前一时刻只包含i-1种物品,不包含第i种物品,所以不可能从i-1时刻转移过来。
    
                dp[j] = max(dp[j], dp[j-weight[i]]+value[i])
    
        return dp[bag_weight]
    

     再来2个灵魂拷问彻彻底底弄清完全背包。
    1.内外for循环的顺序能否颠倒?
     可以的无所谓,代码如下,状态转移方程不变。

    	for j in range(0, bag_weight+1):
    		for i in range(0, len(weight)):
    			if weigth[i]<=j:
    				dp[j] = max(dp[j], dp[j-weight[i]]+value[i])
    

     因为dp[j] 是根据 下标j之前所对应的dp[j]计算出来的。 只要保证下标j之前的dp[j]都是经过计算的就可以咯,毕竟正序遍历,可以选无数次物品哈哈。

    2.用2维数组实现的话如何?
     01背包二维dp数组实现中,状态转移方程为:

    # 背包容量放的下第i个物品,可放可不放
    # 不放:那就等于前i-1个物品(在容量j中)的最大价值
    # 放:那就等于前i-1个物品(在容量j-weight[i]中)的最大价值
    dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]]+value[i])
    

     完全背包二维数组实现中,将状态转移方程改为:

    # 背包容量放的下第i 种 物品,可放可不放
    # 不放:那就等于前i-1 种 物品(在容量j中)的最大价值
    # 放:那就等于前i 种 物品(在容量j-weight[i]中)的最大价值。
    #选择放的时候,不取决与前一时刻的状态,
    #因为前一时刻只包含i-1 种 物品,不包含第i 种 物品,所以不可能从i-1时刻转移过来。
    dp[i][j] = max(dp[i-1][j], dp[i][j-weight[i]]+value[i])
    

     听说那些变种题目,在这两个for循环顺序上会有很大区别,要注意题目稍有变换for循环顺序很关键。(因为这两个for循环的顺序的调换在一些问题上会涉及到组合或排列问题,所以有时不能调换,针对问题看情况。只有纯完全背包类型的问题才可以调换。)
     对于背包问题,递推公式算是容易的,难是难在遍历顺序上,如果把遍历顺序搞透,才算真正理清了。

    🚀三、多重背包问题:

    在这里插入图片描述

    def bag_multi():
        weight = [1, 3, 4]
        value = [15, 20, 30]
        limit = [2,2,1]
        bag_weight = 4
    
        # dp[j]表示容量为j的背包能放下物品的最大价值
        dp = [0]*(bag_weight+1)
    
        # 外循环遍历物品种类
        for i in range(0, len(weight)):
            # 内循环遍历背包容量,逆序,因为我将其看成了一个:01背包问题
            # 为何可以看出01背包问题。因为相当于我将每个种类里的物品进行了各种数量的捆绑后看出一个整体,只能选一次(当然前提是也不能超过背包容量:j)
            # 具体操作是在内层循环里开多一层循环,遍历每种满足条件的捆绑情况,看哪种捆绑情况价值最大。
            for j in range(bag_weight, weight[i]-1, -1):
                k=1
                while(k<=limit[i] and k*weight[i]<=j):
                    dp[j] = max(dp[j], dp[j-k*weight[i]] + k*value[i])
                    k += 1
    
        return dp[bag_weight]
    

     还有一种时间复杂度一样但是空间会有点浪费的方法就是:
     将每个种类的物品都看成只能选1次的物品,扩展一下weight和value列表,然后就可以直接看成一个01背包问题了。
     然后还有一种用了二进制思想去优化时间复杂度的方法具体自己百度咯。因为听说leetcode上没有多重背包类型的题目,面试也会比较少出。基本都是01背包或完全背包的变种类型题目。

    🚀四、01背包存在问题:

    在这里插入图片描述

    def bag_01_exist():
        weight = [1, 3, 4, 2, 2]
        bag_weight = 13
    
        # dp[j]能否刚好装满容量为j的背包
        dp = [False]*(bag_weight+1)
        # dp[j]都是依赖j以前的索引的dp值来更新的,若dp[0]=False。那整个dp数组都为False了。
        dp[0] = True
    
        # 外循环遍历物品
        for i in range(0, len(weight)):
            # 内循环遍历背包容量,逆序和01背包一样
            for j in range(bag_weight, weight[i]-1, -1):
    
                #在i-1状态时,dp[j]表示从前i-1个物品中选取物品是否能刚好装满容量为j的背包
                #dp[j-weight[i]]表示在背包容量为j-weight[i]时,从前i个物品中选取物品是否能刚好装满容量为j的背包。
                #所以将上面两种情况之一满足True,那肯定dp[j]为True
                dp[j] = dp[j] or dp[j-weight[i]]
    
        return dp[bag_weight]
    
    print(bag_01_exist())
    

    🚀五、完全背包存在问题:

    在这里插入图片描述

    def bag_full_exist():
        weight = [3,11,12,15]
        bag_weight = 10
    
        # dp[j]能否刚好装满容量为j的背包
        dp = [False]*(bag_weight+1)
        # dp[j]都是依赖j以前的索引的dp值来更新的,若dp[0]=False。那整个dp数组都为False了。
        dp[0] = True
    
        # 外循环遍历每种物品
        for i in range(0, len(weight)):
            # 内循环遍历背包容量,正序
            for j in range(weight[i], bag_weight+1):
    
                #在i-1状态时,dp[j]表示从前i-1种物品中选取物品是否能刚好装满容量为j的背包
                #dp[j-weight[i]]表示在背包容量为j-weight[i]时,从前i种物品中选取物品是否能刚好装满容量为j的背包。
                #所以将上面两种情况之一满足True,那肯定dp[j]为True
    
                dp[j] = dp[j] or dp[j-weight[i]]
        return dp[bag_weight]
    
    print(bag_full_exist())
    

    🚀六、01背包组合问题:

    在这里插入图片描述
     也就是01背包问题的扩展,求装满背包的组合数。解释看代码即可:

    def bag_01_combine():
        weight = [1, 3, 4, 2, 2]
        bag_weight = 4
    
        # dp[j]表示装满容量为j的背包一共有dp[j]种组合方法
        dp = [0]*(bag_weight+1)
    
        # 即背包容量为0,有1种方法即装0件。不能初始化为0毕竟从状态转移公式可见,
        # dp[j]都是依赖j以前的索引的dp值来更新的,若dp[0]=0。那整个dp数组都为0了。
        dp[0] = 1
    
        # 外循环遍历物品
        for i in range(0, len(weight)):
            # 内循环遍历背包容量,逆序和01背包一样
            for j in range(bag_weight, weight[i]-1, -1):
    
                #在i-1状态时,dp[j]表示从前i-1个物品中选取物品装满背包容量为j的组合数。当然我加上物品i后的组合数是不变的
                #dp[j-weight[i]]表示在背包容量为j-weight[i]时,从前i个物品中选取物品装满容量为j的背包的组合数。
                #所以将上面两个加起来就是下式,表示:在背包容量为j时的组合数等于,前i-1个物品的组合数(背包容量为j)加上从前i个物品中选取物品的组合数(背包容量为j-weight[i])
                dp[j] += dp[j-weight[i]]
    
        return dp[bag_weight]
    
    print(bag_01_combine())
    

    🚀七、完全背包组合问题:

    在这里插入图片描述
     弄懂01背包组合问题,这个很好懂,不过要注意了,求组合数的问题,内外2个for循环可不能颠倒,颠倒了就变成了求组合数或排列数问题,这是不一样的。要十分注意。

    def bag_full_combine():
        weight = [1, 3, 4]
        bag_weight = 4
    
        # dp[j]表示装满容量为j的背包一共有dp[j]种组合方法
        dp = [0]*(bag_weight+1)
    
        # 即背包容量为0,有1种方法即装0件。不能初始化为0毕竟从状态转移公式可见,
        # dp[j]都是依赖j以前的索引的dp值来更新的,若dp[0]=0。那整个dp数组都为0了。
        dp[0] = 1
    
        # 外循环遍历每种物品
        for i in range(0, len(weight)):
            # 内循环遍历背包容量,正序
            for j in range(weight[i], bag_weight+1):
    
                #在i-1状态时,dp[j]表示从前i-1 种 物品中选取物品装满背包容量为j的组合数。当然我加上物品i后的组合数是不变的
                #dp[j-weight[i]]表示在背包容量为j-weight[i]时,从前i种物品中选取物品装满容量为j的背包的组合数。
                #所以将上面两个加起来就是下式,表示:在背包容量为j时的组合数等于,前i-1 种 物品的组合数(背包容量为j)加上从前 i 种物品中选取物品的组合数(背包容量为j-weight[i])
    
                dp[j] += dp[j-weight[i]]
    
        return dp[bag_weight]
    
    print(bag_full_combine())
    

    下面解释下内外for循环的顺序问题:

     因为先遍历物品再遍历背包,就是组合问题:

    for i in range(0, len(weight)):
    	for j in range(weight[i], bag_weight+1):
    		dp[j] += dp[j-weight[i]]
    

     假设有两个物品:weight[0] = 1,weight[1] = 3。(目标是凑齐target=4)
     那么就是先把1加⼊计算,然后再把3加⼊计算,得到的⽅法数量只有{1, 3}这种情况。⽽不会出现{3, 1}的情况。
     for循环时虽然都会出现以下情况,让你误以为{1, 3} 和 {3, 1}都算进去了。你从头到尾推一遍。其实你会发现,下面1中的dp[3]再凑一个1就可以凑成4(但是这个3是由3个1凑来的),而下面2中的dp[1]再凑一个3就能凑成4(但是这个3就是一个3,而不是3个1凑成的)。所以只会考虑1,3这种情况(因为物品遍历放在外层,3只能出现在1后面!):

    1.   dp[4] += dp[4-1] 即dp[4] += dp[3]
    2.   dp[4] += dp[4-3] 即dp[4] += dp[1]
    

     自己手算一遍就知道了,类似的道理for循环颠倒就是排列了。

     而如果先遍历背包再遍历物品,就是排列问题:

    for j in range(0, bag_weight+1):
    	for i in range(0, len(weight)):
    		if j >= weight[i]: 
    			dp[j] += dp[j-weight[i]]
    

     背包容量的每⼀个值,都是经过 1 和 3的计算,包含了{1, 3} 和 {3, 1}两种情况。

     如果求组合数就是外层for循环遍历物品,内层for遍历背包。
     如果求排列数就是外层for遍历背包,内层for循环遍历物品。

    🚀八、完全背包排列问题:

    在这里插入图片描述
     也就是调换下for循环的位置即可,上面完全背包组合问题中已经作过解释了:

    def bag_full_permutation():
        weight = [1, 5]
        bag_weight = 6
    
        # dp[j]表示装满容量为j的背包一共有dp[j]种组合方法
        dp = [0]*(bag_weight+1)
    
        # 即背包容量为0,有1种方法即装0件。不能初始化为0毕竟从状态转移公式可见,
        # dp[j]都是依赖j以前的索引的dp值来更新的,若dp[0]=0。那整个dp数组都为0了。
        dp[0] = 1
    
        # 外循环遍历背包
        for j in range(0, bag_weight + 1):
    
            # 内循环遍历物品种类
            for i in range(0, len(weight)):
                if j >= weight[i]:
                    #在i-1状态时,dp[j]表示从前i-1 种 物品中选取物品装满背包容量为j的组合数。当然我加上物品i后的组合数是不变的
                    #dp[j-weight[i]]表示在背包容量为j-weight[i]时,从前i种物品中选取物品装满容量为j的背包的组合数。
                    #所以将上面两个加起来就是下式,表示:在背包容量为j时的组合数等于,前i-1 种 物品的组合数(背包容量为j)加上从前 i 种物品中选取物品的组合数(背包容量为j-weight[i])
                    dp[j] += dp[j-weight[i]]
        return dp[bag_weight]
    
    print(bag_full_permutation())
    


    本篇是背包问题的Python实现,关于java实现请看这:
    【1】DP经典回顾:背包问题

    一些参考链接:
     这篇会讲解一些背包问题的变种题目及常用模板:
    【1】一篇文章吃透背包问题!(细致引入+解题模板+例题分析+代码呈现)
     这篇及其系列的DP文章讲解的原理比较全面不错:
    【2】动态规划:关于01背包问题,你该了解这些!

    展开全文
  • 完全背包

    2019-03-30 22:38:50
    一个旅行者随身携带一个背包,可以放入背包的物品有n种,每种物品的重量和价值分别是wi,viwi,vi,如果背包的最大容量限制是bb,每种物品可以放多个,怎样选择放入背包的物品以使得背包的价值最大? 1) 子问题定义:F[i]...

    问题描述:

    一个旅行者随身携带一个背包,可以放入背包的物品有n种,每种物品的重量和价值分别是wi,viwi,vi,如果背包的最大容量限制是bb,每种物品可以放多个,怎样选择放入背包的物品以使得背包的价值最大?

            1) 子问题定义:F[i][j]表示前i种物品中选取若干件物品放入剩余空间为j的背包中所能得到的最大价值。

            2) 根据第i种物品放多少件进行决策

            其中F[i-1][j-K*C[i]]+K*W[i]表示前i-1种物品中选取若干件物品放入剩余空间为j-K*C[i]的背包中所能得到的最大价值加上k件第i种物品;

           设物品种数为N,背包容量为V,第i种物品体积为C[i],第i种物品价值为W[i]。

           与01背包相同,完全背包也需要求出NV个状态F[i][j]。但是完全背包求F[i][j]时需要对k分别取0,…,j/C[i]求最大F[i][j]值,耗时为j/C[i]。那么总的时间复杂度为O(NV∑(j/C[i]))
     

    伪代码如下:

     F[0][] ← {0}
     
         F[][0] ← {0}
     
         for i←1 to N
     
             do for j←1 to V
     
                 do for k←0 to j/C[i]
     
                    if(j >= k*C[i])
     
                         then F[i][k] ← max(F[i][k],F[i-1][j-k*C[i]]+k*W[i])
     
         return F[N][V]

     简单优化:

            若两件物品满足C[i] ≤C[j]&&W[i] ≥W[j]时将第j种物品直接筛选掉。因为第i种物品比第j种物品物美价廉,用i替换j得到至少不会更差的方案。

           这个筛选过程如下:先找出体积大于背包的物品直接筛掉一部分(也可能一种都筛不掉)复杂度O(N)。利用计数排序思想对剩下的物品体积进行排序,同时筛选出同体积且价值最大的物品留下,其余的都筛掉(这也可能一件都筛不掉)复杂度O(V)。

    完全背包问题有一个很简单有效的优化,是这样的:若两件物品i、j 满足Ci ≤ Cj且Wi ≥ Wj,则将可以将物品j 直接去掉,不用考虑。这个优化的正确性是显然的:任何情况下都可将价值小费用高的j 换成物美价廉的i,得到的方案至少不会更差。对于随机生成的数据,这个方法往往会大大减少物品的件数,从而加快速度。然而这个并不能改善最坏情况的复杂度,因为有可能特别设计的数据可以一件物品也去不掉。

    优化代码:

    int main()
    {
    
        int n,w;
        cin>>n>>w;
        map<int,int > m;
    
        int i,wi,vi;
    
        for(i=0;i<n;i++)
        {
            cin>>wi>>vi;
            if(wi<=w)  // 费用大于w的去掉
            {
                if(m.find(wi)!=m.end())
                {
                    if(m[wi]<vi)  //费用(体积)相同时 选择更大的价值
                    {
                        m[wi]=vi;
                    }
                }
                else
                {
                    m[wi]=vi;
                }
            }
        }
    
        map<int,int>::iterator it;
        it=m.begin();
    
        while(it!=m.end())
        {
            cout<<it->first<<"    "<<it->second<<endl;
            it++;
        }
    
        return 0;
    }

    转化为01背包

    01 背包问题是最基本的背包问题,我们可以考虑把完全背包问题转化为01 背包问题来解。 
    最简单的想法是,考虑到第i 种物品最多选⌊V /Ci⌋ 件,于是可以把第i 种物品转化为⌊V /Ci⌋ 件费用及价值均不变的物品,然后求解这个01 背包问题。这样的做法完全没有改进时间复杂度,但这种方法也指明了将完全背包问题转化为01 背包问题的思路:将一种物品拆成多件只能选0 件或1 件的01 背包中的物品。更高效的转化方法是:把第i 种物品拆成费用Ci * 2^k、价值为Wi * 2^k 的若干件物品,其中k 取遍满足Ci*2^k ≤ V 的非负整数。这是二进制的思想。因为,不管最优策略选几件第i 种物品,其件数写成二进制后,总可以表示成若干个2^k 件物品的和。这样一来就把每种物品拆成O(log ⌊V /Ci⌋) 件物品,是一个很大的改进。

    代码如下:

    int main()
    {
        int n;
        cin>>n;
        while(n--)
        {
    
            int money;
            cin>>money;
    
            int i;
    
            for(i=0;i<3;i++)
            {
                for(int j=0;j<=money;j++)
                {
                    if(j>=v[i])
                    {
                        dp_1[j]=max(dp_1[j],dp_1[j-v[i]]+v[i]);
                    }
                }
            }
    
            cout<<money-dp_1[money]<<endl;
        }
        return 0;
    }

    抽象函数伪代码

    完全背包的思想和01背包的思想非常相似,两者的区别就在01背包是一个物体只有一个,而完全背包的物体是多个的。如果能把这一点给搞懂就很好理解了。

    01背包具体参考这篇博客

    https://mp.csdn.net/mdeditor/88808637#

    展开全文
  • 文章目录背包问题dp定义关于背包的两个关键点01背包二维先遍历物品先遍历背包一维(倒着遍历防止被重复放入,详解看图)完全背包什么是完全背包问题[279. 完全平方数]...

    背包问题


    Image

    只需要知道0-1背包和完全背包问题就完全足够了

    0-1背包有以下的特点

    • 有限个物体(有重量和价值),每个物体只有一个
    • 每个物体你都可以任选,可选也可以不选
    • 有限制(上限或者下限)而且这个限制不能太

    Image

    dp定义

    对于背包问题,有一种写法, 是使用二维数组,即dp[i][j] 表示从下标为[0-i]的物品里任意取,放进容量为j的背包,价值总和最大是多少

    关于背包的两个关键点

    • 第一怎么01背包降维的时候要反序遍历
    • 第二为什么完全背包问题的时候组合的时候先遍历物品,后遍历背包容量

    01背包

    接下来来详细解答这两个关键:

    以下面的例子为例

    假设你是一个小偷,背着一个可装下4磅东西的背包,你可以偷窃的物品如下:

    img

    为了让偷窃的商品价值最高,你该选择哪些商品?

    这就是典型的背包问题
    物品也就是nums
    背包容量也就是 target
    
    第一种解法: 定义二维dp数组
    dp[i][j]: 表示在前i个物品中能放进j容量能有多少种方法
    也就是说每一物体只有两种选择为正数或者负数
    

    对于01背包问题先遍历物品和先遍历背包都是一样的只是先遍历物品更好理解

    二维

    先遍历物品

    // weight数组的大小 就是物品个数
    for(int i = 1; i < weight.size(); i++) { // 遍历物品
        for(int j = 0; j <= bagWeight; j++) { // 遍历背包容量 
            if (j < weight[i]) dp[i][j] = dp[i - 1][j]; // 这个是为了展现dp数组里元素的变化
            else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
            
        }
    }
    

    先遍历背包

    // weight数组的大小 就是物品个数
    for(int j = 0; j <= bagWeight; j++) { // 遍历背包容量
        for(int i = 1; i < weight.size(); i++) { // 遍历物品
            if (j < weight[i]) dp[i][j] = dp[i - 1][j];
            else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
        }
    }
    

    一维(倒着遍历防止被重复放入,详解看图)

      for(int i = 0; i < weight.size(); i++) { // 遍历物品
            for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
                dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
            }
        }
    

    参考链接

    完全背包

    完全背包的特点就是物品有无限个想怎么拿就怎么拿,所以对于纯完全背包问题先遍历背包和先遍历物品是一样的,但是如果变化那么区别就在于我们的遍历顺序

    什么是完全背包问题

    有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i],得到的价值是value[i] 。每件物品都有无限个(也就是可以放入背包多次),求解将哪些物品装入背包里物品价值总和最大。
    

    注意这里说的是,求解放入背包的物品价值总和最大,也就是说你这物品的放入是有序还是无序我都可以的,不管你怎么放入,这个是完全背包的一个关键点

    所以在这里纯完全背包问题就是可以先遍历物品或者先遍历背包都是可以的

    279. 完全平方数

    难度中等880

    给定正整数 n,找到若干个完全平方数(比如 1, 4, 9, 16, ...)使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

    给你一个整数 n ,返回和为 n 的完全平方数的 最少数量

    完全平方数 是一个整数,其值等于另一个整数的平方;换句话说,其值等于一个整数自乘的积。例如,14916 都是完全平方数,而 311 不是。

    示例 1:

    输入:n = 12
    输出:3 
    解释:12 = 4 + 4 + 4
    

    示例 2:

    输入:n = 13
    输出:2
    解释:13 = 4 + 9
    

    先遍历物品后遍历背包

    class Solution {
    public:
        int numSquares(int n) {
            // 首先这就是这个纯完全背包问题,也就是说物体是小于n的所有完全平方数,
            // 背包就是n,至于物品是否的有序或者无序放入就无所谓了,你随便放
    
            // 所以先遍历背包还是先遍历物品都是可以的
    
            /* 
                这里先遍历物品
             */
    
             // 先求符合条件的完全平方数
             vector<int> data;
             for(int i=1;i<=n;i++) {
                 if(i*i<=n) {
                     data.push_back(i*i);
                 } else {
                     break;
                 }
             }
    
    
             // 定义dp
             vector<int> dp(n+1,0);
            // 初始化
            for(int i=1;i<=n;i++) {
                if(i%data[0]==0) {
                    dp[i]=i/data[0];
                }
            }
    
             for(int i=1;i<data.size();i++) {  // 先遍历物品
                 for(int j=data[i] ; j<=n; j++ ) {  // 后遍历容量
                     dp[j] = min(dp[j],dp[j-data[i]]+1);
                 }
             }
    
             return dp[n];
    
        }
    };
    

    解法2

    public:
        int numSquares(int n) {
            vector<int> dp(n + 1, INT_MAX);
            dp[0] = 0;
            for (int i = 0; i <= n; i++) { // 遍历背包
                for (int j = 1; j * j <= i; j++) { // 遍历物品
                    dp[i] = min(dp[i - j * j] + 1, dp[i]);
                }
            }
            return dp[n];
        }
    };
    

    这里dp[0]=0的含义就和上面的不一样,,这里dp[0]代表的是没有物品的时候,各个容量所能放的最大价值,其实也是通过二维状态压缩过来的

    先遍历背包后遍历物体

    class Solution {
    public:
        int numSquares(int n) {
            // 首先这就是这个纯完全背包问题,也就是说物体是小于n的所有完全平方数,
            // 背包就是n,至于物品是否的有序或者无序放入就无所谓了,你随便放
    
            // 所以先遍历背包还是先遍历物品都是可以的
    
            /* 
                这里先遍历背包
             */
    
             // 先求符合条件的完全平方数
             vector<int> data;
             for(int i=1;i<=n;i++) {
                 if(i*i<=n) {
                     data.push_back(i*i);
                 } else {
                     break;
                 }
             }
    
    
             // 定义dp
             vector<int> dp(n+1,INT_MAX);
            // 初始化
            dp[0]=0;
            // 代表容量为0的时候个数为0
    
            for(int i=0;i<=n;i++) { // 先遍历背包,不用初始化,因为背包容量为0,肯定放不下
                for(int j=0;j<data.size();j++) {
                   if(i>=data[j]) {
                      dp[i] = min(dp[i],dp[i-data[j]]+1);
                   }
                }
            }
    
             return dp[n];
    
        }
    };
    

    状态压缩过程

    要考虑插入顺序的完全背包问题

    博客地址

    总结

    总结

    展开全文
  • 第i种物品的费用是c[i]...求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。基本思路这个问题非常类似于01背包问题,所不同的是每种物品有无限件。也就是从每种物品的角度考虑,与它相...

    http://www.concretevitamin.com.cn/informatics/Pack/P02.html

    题目

    有N种物品和一个容量为V的背包,每种物品都有无限件可用。第i种物品的费用是c[i],价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。

    基本思路

    这个问题非常类似于01背包问题,所不同的是每种物品有无限件。也就是从每种物品的角度考虑,与它相关的策略已并非取或不取两种,而是有取0件、取1件、取2件……等很多种。如果仍然按照解01背包时的思路,令f[i][v]表示前i种物品恰放入一个容量为v的背包的最大权值。仍然可以按照每种物品不同的策略写出状态转移方程,像这样:

    f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k*c[i]<=v}

    这跟01背包问题一样有O(VN)个状态需要求解,但求解每个状态的时间已经不是常数了,求解状态f[i][v]的时间是O(v/c[i]),总的复杂度可以认为是O(V*Σ(V/c[i])),是比较大的。

    将01背包问题的基本思路加以改进,得到了这样一个清晰的方法。这说明01背包问题的方程的确是很重要,可以推及其它类型的背包问题。但我们还是试图改进这个复杂度。

    一个简单有效的优化

    完全背包问题有一个很简单有效的优化,是这样的:若两件物品i、j满足c[i]<=c[j]且w[i]>=w[j],则将物品j去掉,不用考虑。这个优化的正确性显然:任何情况下都可将价值小费用高得j换成物美价廉的i,得到至少不会更差的方案。对于随机生成的数据,这个方法往往会大大减少物品的件数,从而加快速度。然而这个并不能改善最坏情况的复杂度,因为有可能特别设计的数据可以一件物品也去不掉。

    这个优化可以简单的O(N^2)地实现,一般都可以承受。另外,针对背包问题而言,比较不错的一种方法是:首先将费用大于V的物品去掉,然后使用类似计数排序的做法,计算出费用相同的物品中价值最高的是哪个,可以O(V+N)地完成这个优化。这个不太重要的过程就不给出伪代码了,希望你能独立思考写出伪代码或程序。

    转化为01背包问题求解

    既然01背包问题是最基本的背包问题,那么我们可以考虑把完全背包问题转化为01背包问题来解。最简单的想法是,考虑到第i种物品最多选V/c[i]件,于是可以把第i种物品转化为V/c[i]件费用及价值均不变的物品,然后求解这个01背包问题。这样完全没有改进基本思路的时间复杂度,但这毕竟给了我们将完全背包问题转化为01背包问题的思路:将一种物品拆成多件物品。

    更高效的转化方法是:把第i种物品拆成费用为c[i]*2^k、价值为w[i]*2^k的若干件物品,其中k满足c[i]*2^k<=V。这是二进制的思想,因为不管最优策略选几件第i种物品,总可以表示成若干个2^k件物品的和。这样把每种物品拆成O(log V/c[i])件物品,是一个很大的改进。

    但我们有更优的O(VN)的算法。

    O(VN)的算法

    这个算法使用一维数组,先看伪代码:

    for i=1..N

    for v=0..V

    f[v]=max{f[v],f[v-cost]+weight}

    你会发现,这个伪代码与P01的伪代码只有v的循环次序不同而已。为什么这样一改就可行呢?首先想想为什么P01中要按照v=V..0的逆序来循环。这是因为要保证第i次循环中的状态f[i][v]是由状态f[i-1][v-c[i]]递推而来。换句话说,这正是为了保证每件物品只选一次,保证在考虑“选入第i件物品”这件策略时,依据的是一个绝无已经选入第i件物品的子结果f[i-1][v-c[i]]。而现在完全背包的特点恰是每种物品可选无限件,所以在考虑“加选一件第i种物品”这种策略时,却正需要一个可能已选入第i种物品的子结果f[i][v-c[i]],所以就可以并且必须采用v=0..V的顺序循环。这就是这个简单的程序为何成立的道理。

    值得一提的是,上面的伪代码中两层for循环的次序可以颠倒。这个结论有可能会带来算法时间常数上的优化。

    这个算法也可以以另外的思路得出。例如,将基本思路中求解f[i][v-c[i]]的状态转移方程显式地写出来,代入原方程中,会发现该方程可以等价地变形成这种形式:

    f[i][v]=max{f[i-1][v],f[i][v-c[i]]+w[i]}

    将这个方程用一维数组实现,便得到了上面的伪代码。

    最后抽象出处理一件完全背包类物品的过程伪代码:

    procedure CompletePack(cost,weight)

    for v=cost..V

    f[v]=max{f[v],f[v-c[i]]+w[i]}

    总结

    完全背包问题也是一个相当基础的背包问题,它有两个状态转移方程,分别在“基本思路”以及“O(VN)的算法“的小节中给出。希望你能够对这两个状态转移方程都仔细地体会,不仅记住,也要弄明白它们是怎么得出来的,最好能够自己想一种得到这些方程的方法。事实上,对每一道动态规划题目都思考其方程的意义以及如何得来,是加深对动态规划的理解、提高动态规划功力的好方法。

    publicclassCompletePack {

    publicCompletePack(intV) {

    this.V = V;

    this.maxValues =newint[this.V +1];

    }

    privateintV;

    privateint[] maxValues;

    publicintadd(Goods goods) {

    if(goods.getCost() > V) {

    returngetMaxValue();

    }

    for(intv = goods.getCost(); v <= V; v++) {

    maxValues[v] = Math.max(maxValues[v],

    maxValues[v - goods.getCost()] + goods.getValue());

    }

    returngetMaxValue();

    }

    publicintgetMaxValue() {

    returnmaxValues[V];

    }

    /**

    * @param args

    */

    publicstaticvoidmain(String[] args) {

    CompletePack pack =newCompletePack(100);

    for(inti =0; i 10; i++) {

    Goods g1 =newGoods((int) (Math.random() *100), (int) (Math

    .random() *100));

    pack.add(g1);

    System.out.println(g1.getCost() +","+ g1.getValue() +"   Max: "

    + pack.getMaxValue());

    }

    }

    }

    展开全文
  • 完全背包问题(详细解答)

    千次阅读 多人点赞 2021-03-22 20:23:54
    首先完全背包问题需要01背包问题做铺垫,如果读者01背包问题没有解决,一定要理解之后,在看完全背包问题,包括01背包的优化! 这里是01背包 这里是01背包的全部优化 好,我们开始完全背包! 完全背包定义 有N种物品和一个...
  • 上一节中,我们介绍了0-1背包问题,接下来,我们来学习一下背包问题的其他变形问题,今天要学习的是完全背包问题。1、简介有 N 种物品和一个容量为 W 的背包,每种物品都有无限件可用。第 i 种物品的重量是 w[i],...
  • 完全背包算法洛谷例题精选,适合入门算法同学食用!
  • C++完全背包

    2019-08-13 14:52:34
    给出N个物品(一个物品可以选择多次,没有限制),背包最大承重为M,每个物品有一个重量w,一个价值v。如何选择才能在重量不超过M的情况下,使选择的物品的价值总和最大。
  • 动态规划:完全背包、多重背包

    万次阅读 多人点赞 2018-07-20 16:17:56
     完全背包:有N种物品和一个容量为V的背包,每种物品都有无限件可用。第i种物品的费用是c[i],价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。   多重背包:有N种...
  • 完全背包详解

    2018-08-10 16:14:00
    完全背包问题描述 有一个最多可以装质量为W的背包,有N件物品,每件物品都有无数件,第i件物品的质量为w [ i ] 价值为 v[ i ]。 问:在不超过背包容量下,可以获得的最大价值是多少? (注:如果不会01背包的请大家...
  • C++实现。对0/1背包问题应用3种方法(动态规划、...对背包问题和完全背包问题应用动态规划和贪婪算法,通过实例比较求解速度。 随机生成500个0/1背包问题(问题规模可以相对较小),使用贪心算法和动态规划进行求解。
  • 0-1背包与完全背包的唯一的区别在于0-1背包每个物品只能使用一次,但是完全背包可以重复使用。 二.0-1背包空间优化 假设物品编号1~n 重量w[i] 价值v[i] 0-1背包使用的倒叙遍历就是为了避免重复使用同一个物品。 **1...
  • 95、1268:【例9.12】完全背包问题(2020.03.19)A
  • Leetcode动态规划—完全背包问题

    千次阅读 2020-05-12 22:19:02
    前文:Leetcode动态规划——01背包问题 :https://blog.csdn.net/qq_41605114/article/details/106059876 动态规划一般解决最值问题,题目只要问最值,但是不在乎得到最值的解法,基本可以考虑使用动态规划解决...
  • 01背包空间优化 当初学01背包的时候,会有这样一个状态转移方程: 约定: dp[i][j]表示在0~i下标物品中选取,在总金额不超过j的情况下获得的最大价值 v[i]表示第 i 下标的物品的价值 dp[i][j] = max(dp[i-1][j], dp...
  • 完全背包问题和优化

    2020-06-02 12:18:53
    完全背包问题 题意 选取的物品无限 求价值最大值 分析图解 难点:状态计算——第i个物品选(0 - k)个。那么k*v【i】 <= 背包剩余空间 第i个物品,选k个 那么需要加上 k个物品的价值 朴素的算法 /* f[i - 1]...
  • 求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。 基本思路 这个问题非常类似于01背包问题,所不同的是每种物品有无限件。也就是从每种物品的角度考虑,与它相关的策略已并非取或不...
  • 完全背包问题 题目描述 有 N 种物品和一个容量是 V 的背包,每种物品都有无限件可用。 第 i 种物品的体积是 vi,价值是 wi。 求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。输出最大...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 38,565
精华内容 15,426
关键字:

完全背包

友情链接: 15907525.rar