-
背包问题 动态规划_动态规划多类背包问题总结
2021-01-27 02:17:39背包问题顾名思义,就是将一些物品放到一个背包中,背包对物体有重量限制,而我们需要的是背包中物体的总价值尽可能地多,其本质是有约束的优化问题。借用老师上课的图如下:转换为有约束的优化问题的数学表示如下:...作为动态规划(DP)中的经典问题背包问题,有以下三类子问题,分别为:0-1 背包问题、完全背包问题和多重背包问题。卜老师上课提到的主要为 0-1 背包问题。背包问题顾名思义,就是将一些物品放到一个背包中,背包对物体有重量限制,而我们需要的是背包中物体的总价值尽可能地多,其本质是有约束的优化问题。
借用老师上课的图如下:
转换为有约束的优化问题的数学表示如下:
目标函数为每类物品价值总和,约束条件1为每类物品重量和不超过背包限重,约束条件2为每类物品的选取数量约束。不同的背包问题主要差别在于每类物品选取数量的约束,也就是 。
显然,背包问题的本质是线性的有约束的优化问题,理论上也可以用线性规划解决,但这里只分析动态规划方法。
01 "0-1"背包问题
0-1背包问题中,每类物品的选取只有:选-1or 不选-0,即 ,有约束优化问题,表示为如下:
0-1 背包问题老师上课已经讲得很多了,这里直接给出子问题和状态转移方程:
子问题:当背包容量为 j 时,前 i 个物品所能达到的最大价值。
状态转移方程:面对背包容量为 j ,我们需要决策是不是需要放入第 i 个物品。如果包容量 j 放不下第 i 个物品,那么很简单,前 i 个物品所能达到的最大价值就是前 i-1个物品所能达到的最大价值;如果放得下,那么需要分析放第 i 个物品与不放第 i 个物品达到包容量 j 时的价值差异。公式表示如下
借用卜老师课件的数据我们完善一下 OPT 表格如下:
最后我们得到的最优的背包价值为$15,选择的物品为 2kg/$2、1kg/$2、1kg/$1 和4kg/$10。
复杂度分析:OPT 表格中的状态数量为 W*N,W 为背包限重,N 为物品数量,状态转移复杂度为 O(1),综合是时间复杂度为 O(W*N),空间复杂度为 O(W*N),类似背包问题都可以用一维数组更新代替二维数组(因为二维数组是从左往右从上到下按序生成状态值),所以空间复杂度可以优化到 O(W)。
02 完全背包问题
完全背包问题中,每类物品的选择都是不收限制的,也就是说 可以取到正无穷,因此有约束的优化问题表示如下:
首先我们按照常规理解来做:
子问题:当背包容量为 j 时,前 i 个物品所能达到的最大价值。
状态转移方程:面对背包容量为 j ,我们需要决策放入几个第 i 个物品。如果包容量j放不下第 i 个物品,那么很简单,前 i 个物品所能达到的最大价值就是前i-1个物品所能达到的最大价值,与 0-1 背包问题一致;如果放得下,那么需要分析放 0,…,K 个第 i 个物品达到包容量 j 时的价值差异。
公式表示如下:
我们分析下这个时候的时间复杂度,OPT 表格中的状态数量仍然为 W*N,W 为背包限重,N 为物品数量,状态转移复杂度为 O(K),其中 ,时间复杂度为 ,这显然是我们不希望看到的,我们希望仍然像 0-1 背包一样,状态转移复杂度为 O(1)。
一种方法是利用本层 OPT 状态转移数,根据子问题描述,本层的 OPT 状态转移数 已经包含了我们需要决策的第 i 个物品,决策的问题从选择几个第 i 个物品变为是否再次放入一个第 i 个物品。状态转移复杂度重新降为 O(1)。
因此我们将状态转移方程描述为如下:
状态转移方程:面对背包容量为 j ,我们需要决策放入是否再次放入第 i 个物品。如果包容量 j 放不下第 i 个物品,那么前 i 个物品所能达到的最大价值就是前 i-1 个物品所能达到的最大价值;如果放得下,那么需要分析再次放入一个第 i 个物品达到包容量 j 时的价值与不放第 i 个物品达到的最大价值之间的差异。至于在放这个物品前已经放了几个第 i 个物品,由于已经在 经过了决策,因此在决策 时不需要考虑之前背包里已经存在的第 i 个物品的数目。
表达式如下:
同样用例题完成 OPT 表格
最后我们得到的最优的背包价值为$36,选择的物品为 1kg/$2 选 3 件、4kg/$10 选 3 件。
复杂度分析:OPT 表格中的状态数量为 W*N,W 为背包限重,N 为物品数量,状态转移复杂度为 O(1),综合是时间复杂度为 O(W*N),空间复杂度为 O(W*N),同样,该背包问题都可以用一维数组更新代替二维数组,所以空间复杂度可以优化到 O(W)。
值得注意的是:0-1 背包问题在遍历背包容量使可以正序也可以逆序,因为在生成OPT(i,j)使我们用到的只有上层状态数,而在完全背包问题下,遍历背包容量只可以正序,因为我们需要用到同层左侧的状态数,只有先生成左侧状态数,才能生成当前状态数。
03 多重背包问题
多重背包问题提供了每种物品的数量限制,是介于 0-1 背包问题和完全背包问题中间的问题,有约束优化问题表示如下:
我们同样可以按照常规方法去做:
子问题:当背包容量为 j 时,前 i 个物品所能达到的最大价值。
状态转移方程:面对背包容量为 j ,我们需要决策放入几个第 i 个物品。如果包容量 j 放不下第 i 个物品,前 i 个物品所能达到的最大价值就是前i-1个物品所能达到的最大价值;如果放得下,那么需要分析放 0,…, 个第 i 个物品达到包容量 j 时的价值差异。
公式表示如下:
同样分析下时间复杂度,OPT 表格中的状态数量仍然为 W*N,W 为背包限重,N 为物品数量,状态转移复杂度为 , 时间复杂度为
https://www.kancloud.cn/kancloud/pack/70127 背包问题九讲中有对多重背包问题的优化,可以将时间复杂度降低至 。基本的策略是将第 i 种物品划分成若干件,划分标准在 blog 里有详细的说明。这里用 blog 中的一个例子,当 时,物品被划分为系数是 1,2,4,6 的四件物品,当你想取任意数目的 时,都可以用这四个系数组合而成。这样完成了将第 i 种物品分成了 种物品的 0-1 背包问题,复杂度从需要决策放入 0…13 件第 i 种物品变为决策是否放入第 种物品。
同样用例题完成 OPT 表格,我们设置物品数量限制c=(3,3,2,3,2)
最后我们得到的最优的背包价值为$29,选择的物品为 2kg/$2 选 2 件、1kg/$2 选 2 件、1kg/$1 选 1 件、4kg/$10 选 2 件。
04 混合背包问题
混合背包问题将上述三种背包问题进行混合,即有的物品只能放一件,有的可以放多件,有的可以放无穷多件。很显然背包问题涉及的子问题都是完全一致的,即 OPT(i,j)中的状态数表示的含义是完全一致的。因此只需要按类选择不同的状态转移方程就行,如下所示:
05 结语
背包问题作为动态规划中的基础问题,延伸出了许许多多多种多样的变形。通过对背包问题这一基础问题的学习和总结,或许能帮助我们加深对动态规划的理解,也能对那些看上去比较难的算法问题提供解题思路。
-
多维多选的背包问题
2017-11-12 15:47:180-1背包问题是一类典型的组合优化问题,它要求找出n个物体的一个子集使其尽可能的装满容量为W的背包...多约束背包问题等。多选择背包问题定义为有附加约束条件的背包问题,该问题带有互不相关的多选择约束。该问题的特0-1背包问题是一类典型的组合优化问题,它要求找出n个物体的一个子集使其尽可能的装满容量为W的背包。他本质上是一个只有一个约束条件的0-1规划问题,在计算理论上属于NP完全问题,计算复杂性为o(2^n)。随着该问题的发展,产生了该问题的许多变形。例如:多选择背包问题;有界背包问题;无界背包问题;多约束背包问题等。
多选择背包问题定义为有附加约束条件的背包问题,该问题带有互不相关的多选择约束。该问题的特点是只有一个承重有限的背包,将要放入背包的物品被分为相互排斥的若干类,而每类中有若干不同的项目。
多约束背包问题也称为多维背包问题或者多背包问题,它是带有一组约束(重量 尺寸 可靠性等)的背包问题。该问题可以简单描述为n个物品要放入m个称重不同的背包,他与0-1背包问题不同的是,物品放入不同背包的重量是不同的。显然,在多约束背包的问题中,除了确定每个物品是否被放入背包之外,还需要确定他需要放入哪个背包。
多维多选择背包问题是一类特殊的0-1背包问题。问题的描述如下:存在m个背包,其称重分别是Wk(k=1,2,3…m)和n类物品,每类物品又分别有Ii(i=1,2,…n)个物品,其价值分别为Vij(j=1,2,…)而对每一个物品,由于其装入的背包不同而其重量也有所不同,分别为Wijk,该问题要求每一类只选择装入一个物品,在满足背包称重的限制下最大化装入背包的物品总价值。
-
背包问题
2018-11-01 22:29:31复杂约束背包:背包的物品相互约束或依赖 推荐的材料是背包问题九讲,初步学习了0-1背包和完全背包问题。 2. 0-1背包问题 所有的背包问题都可以由0-1背包演化而来。 2.1 问题定义: 有一些物品,这些物品...1.参考资料
背包问题从简单到复杂有:
0-1背包:每种物品只能放入一次
完全背包:每种物品放入次数不限
多维费用背包:物品的费用可能有重量和体积等多个方面
复杂约束背包:背包的物品相互约束或依赖
推荐的材料是背包问题九讲,初步学习了0-1背包和完全背包问题。
2. 0-1背包问题
所有的背包问题都可以由0-1背包演化而来。
2.1 问题定义:
有一些物品,这些物品的重量为[cost i],对应的价值为[value i],将它们装进容量为V的背包,求能获得的最大价值。
2.2 状态定义:
F[i,s]表示将前i件物品装进容量为s的背包时能获得的最大价值,则F[I,V]就是最优解。
2.3 状态转移方程:
F[i,s] = max{ F[i-1,s](不把第i件物品放入背包),F[i-1,s-cost i]+value i(把第i 件物品放入背包)}
2.4 求解算法:
2.5 优化:
上述F数组是I*V,可以优化成一维数组。只要把重量的遍历顺序固定为V---cost i。因为每次更新时要用到前面的值,若从小到大更新,那么后边更新用到的前面的值是更新后的F[i,s-cost i]而非F[i-1, s-cost i]。实际上,求解时通常优先考虑一维数组。
算法改为:
2.6 初始化:
若把题目的要求改为“装满背包时,最大价值多少”,则初始化F[0]=0,F[1..V]为-
,因为s=0,问题可能有解,而没东西可放但是容量不为0,说明没有可行解,用无穷来表示这种状态。
其他的背包问题也要注意初始化问题,根据情况选为负无穷或正无穷。
3. 完全背包问题
3.1 定义
与0-1背包唯一的不同是每种物品数量不限。
3.2 状态转移方程
F[i,s] = max{ F[i-1,s](根本不把第i件物品放入背包),F[i,s-cost i]+value i(把第i 件物品放入背包一次或多次)}唯一的区别在于第二项从i-1到i。
3.3 求解算法
与0-1背包唯一的不同是重量的遍历顺序相反,完全背包的每一项更新要用到前边的更新后的值,所以要从小到大遍历,这样计算F[i,s]时,保证s-cost i的位置上是更新后的F[i, s-cost i]而非F[i-1, s-cost i]。
解背包问题的注意点
1.初始化
2.遍历顺序
3.数组的下标不要越界,比如 cost i可能大于V
4. leetcode
题目定义
非负数组分为两个子数组,两个子数组的和相等。给定一个数组,请问是否能分开。
代码
class Solution(object): def canPartition(self, nums): """ :type nums: List[int] :rtype: bool """ if not nums: return True if len(nums)==1 : return True if nums[0]==0 else False nums_sum = 0 for i in nums: nums_sum += i if nums_sum%2==1: return False v = nums_sum/2 dp = [-1]*(v+1)#因为要装满,所以初始化为-1表示无解 dp[0] = 1#初始化为1表示有解 for i in nums: for idx in range(i,v+1)[::-1]: if dp[idx]==1 or dp[idx-i]==1: dp[idx]=1 return True if dp[-1]==1 else False
因为是要装满且是看问题有无解,所以初始化为-1表示无解,初始化为1表示有解。
问题定义
给一组人民币取值数组,给定一个目标值,求能用人民币数组表示的方案的最小张数,无解返回-1.
代码
class Solution(object): def coinChange(self, coins, amount): if not coins or amount<0: return -1 dp = [10000]*(amount+1) dp[0] = 0 for i in coins: for idx in range(i,amount+1): dp[idx]=min(dp[idx],dp[idx-i]+1) return dp[-1] if dp[-1]<10000 else -1
因为要求最小解,所以无解的初始值为正无穷。这是一个通用技巧。
问题定义
给定0和1的个数,从一个字符串数组中选出不超过0,1的个数的最大字符串数。
代码
class Solution(object): def findMaxForm(self, strs, m, n): if not strs: return 0 dp = [[0 for i in range(n+1)] for j in range(m+1)] for s in strs: c0 = s.count('0') c1 = s.count('1') if c0>m or c1>n: continue for x in range(c0,m+1)[::-1]: for y in range(c1,n+1)[::-1]: dp[x][y] = max(dp[x][y],dp[x-c0][y-c1]+1) return dp[m][n]
与0-1背包的不同是F成了二维数组,分别表示两个约束的取值。也多了一层循环。
python新建二维list使用列表产生式,此处容易踩坑!!!而且行数列数顺序先后要注意!!!
问题定义
给出一个数组和目标值,求 和为目标值(正数)的组合数。注意,顺序不一样算两种解。
代码
from collections import deque class Solution(object): def combinationSum4(self, nums, target): if not nums: return 0 dp = [0]*(target+1) dp[0]=1 for i in range(1,target+1): for num in nums: if i-num>=0: dp[i]+=dp[i-num] return dp[-1]
问题定义
给定数组,每个元素可以取为正或负,问有几种方法使数组所有元素和为目标值。
代码
class Solution(object): def findTargetSumWays(self, nums, S): if not nums: return 0 sum_nums = sum(nums) if S>sum_nums or (sum_nums-S)%2==1: return 0 target = (sum_nums-S)/2 dp = [0]*(target+1) dp[0] = 1 for num in nums: for idx in range(num,target+1)[::-1]: dp[idx] = dp[idx]+dp[idx-num] return dp[-1]
数组全取正数,和为sum_nums,与target差值的一半,就是取值为负的数的和。
问题变成了,选取数组的若干个数,使和为目标值(sum_nums-target)/2。
即0-1背包问题 装满。
-
背包问题(01背包问题,多重背包问题,完全背包问题)——基于python的动态规划
2019-05-28 22:56:141. 0-1背包问题 1.1 题目描述 有一个包和n个物品,包的容量为m,每个物品都有各自的体积和价值,问当从这n个物品中选择多个物品放在包里而物品体积总数不超过包的容量m时,能够得到的最大价值是多少?[对于每个物品...1. 0-1背包问题
1.1 题目描述
有一个包和n个物品,包的容量为m,每个物品都有各自的体积和价值,问当从这n个物品中选择多个物品放在包里而物品体积总数不超过包的容量m时,能够得到的最大价值是多少?[对于每个物品不可以取多次,最多只能取一次,之所以叫做0-1背包,0表示不取,1表示取]
1.2思路
动态规划,根据动态规划解题步骤(建立模型、寻找约束条件、找子问题之间的的递推关系式、填表(区间模型)、得到解)找出0-1背包问题的最优解以及解组成。
1.3 步骤
首先定义:Vi表示标号为i物品的价值,Wi表示标号为i物品的体积。capacity为背包的最大容量。那么一个0-1背包问题的具体步骤如下:
- 建立模型,我们要求在物品总体积限制为capacity的情况下,尽可能装下价值高的物品组合,其模型如下:
- 寻找状态转换方程,即子问题之间的递推关系,我们令V(i,j)表示当前背包为容量 j,前 i 个物品最佳组合对应的价值最优解,那么就有两种可能:
a)包的容量比该商品体积小,即j < Vi,装不下第i个物品。此时背包容量为j,前i个物品的最优解与背包容量为j,前i-1个物品最佳组合对应的最优解是一样的,即V(i,j)=V(i-1,j)
b)当包的容量等于或大于该商品的体积,即j >= Vi,能装下第i个物品。那无非有两种情况,在前i个物品,背包容量为j的最优组合里有第i个物品,但同时占据了背包Wj个容量,V(i,j) = V(i-1,j-Wi)+Vi;在前i个物品,背包容量为j的最优组合里没有第i个物品,此时V(i,j) = V(i-1,j)。所以,根据最优性原理,背包容量为j,前i个物品的最优解V(i,j) 要取这两种情况的最大值,V(i,j) = max{V(i-1,j),V(i-1,j-Wi)+Vi},
由此可以得出递推关系式:
3. 根据递推公式进行逐行填表,初始化表V(i,o) = 0,V(0,j) = 0,表的列维度从0到n,行维度从0到capacity。
4. 根据填表过程,编写代码。1.3 举例
有如下几种物品,物品的价值和体积如表所示:
首先定义:Vi表示标号为i物品的价值,Wi表示标号为i物品的体积。另外背包的总体积为10。1.3.1 填表
填表过程如下:
1.4 python实现
def zeroOneBag(num,capacity,weightList,valueList): valueExcel= [[0 for j in range(capacity + 1)] for i in range(num + 1)] for i in range(1,num+1): for j in range(1,capacity+1): valueExcel[i][j] = valueExcel[i - 1][j] if j >= weightList[i-1] and valueExcel[i][j] < (valueExcel[i - 1][j - weightList[i - 1]] + valueList[i - 1]): valueExcel[i][j] = (valueExcel[i - 1][j - weightList[i - 1]] + valueList[i - 1]) return valueExcel print(zeroOneBag(5,10,[2,2,6,5,4],[6,3,5,4,6])) # 输出结果为: [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 6, 6, 6, 6, 6, 6, 6, 6, 6], [0, 0, 6, 6, 9, 9, 9, 9, 9, 9, 9], [0, 0, 6, 6, 9, 9, 9, 9, 11, 11, 14], [0, 0, 6, 6, 9, 9, 9, 10, 11, 13, 14], [0, 0, 6, 6, 9, 9, 12, 12, 15, 15, 15]]
因此该问题的价值最大组合为15。
1.4.1 算法优化
上面这种写法的时间复杂度为o(nc),空间复杂度也为o(nc)。时间复杂度不能在优化了,但是空间复杂度可以进行优化,使之降低到o(c)。
def zeroOneBagOpt(num,capacity,weightList,valueList): valueRes = [0 for i in range(capacity+1)] for i in range(1, num + 1): for j in range(capacity, 0, -1): if j >= weightList[i-1]: valueRes[j] = max(valueRes[j-weightList[i-1]]+valueList[i-1], valueRes[j]) # i变一次,数组的更新一次,利用数组的不断更新,达到上面的方法动态规划的目的。 # 当j遍历更新完一遍valueRes,valueRes就相当于完成上边方法中表第i+1行的填充. # 必须从后向前遍历和判断储存结果的数组,因为valueRes[j-weightList[i-1]]+valueList[i-1]就相当于V(i-1,j-Wi)+ Vi # 判断第i个物品是否是最优解的时候,需要以i-1的情况为基础,不能掺杂有关第i个物品的信息, # 如果从前往后遍历,那么valueRes[:j]的数是判断了i之后的,会产生错误。 # 这里的value[j]即为上一次最佳结果,从后向前可以在遍历到j的未知的时候,不破坏j前面的上一次的最佳结果。 # return valueRes print(zeroOneBagOpt(5,10,[2,2,6,5,4],[6,3,5,4,6])) # 输出结果为:[0, 0, 6, 6, 9, 9, 12, 12, 15, 15, 15]
1.4.2 找到最佳组合的构成
通过上面的方法可以求出背包问题的最优解,但还不知道这个最优解由哪些商品组成,故要根据最优解回溯找出解的组成,根据填表的原理可以有如下的寻解方式:
- V(i,j)=V(i-1,j)时,说明没有选择第i 个商品,则回到V(i-1,j);
- V(i,j)!=V(i-1,j)时,说明装了第i个商品,该商品是最优解组成的一部分,一定有V(i,j)=V(i-1,j-w(i))+v(i),随后我们得回到装该商品之前,即回到V(i-1,j-w(i));
- 重复1,2,一直遍历到i=0结束为止,所有解的组成都会找到。
最优解的组成由第1个,第2个,第5个。
def showRes(num,capacity,weightList,valueExcel): indexRes = [] j = capacity for i in range(num,0,-1): if valueExcel[i][j] != valueExcel[i-1][j]: indexRes.append(i) j -= weightList[i-1] return indexRes valueExcel = (zeroOneBag(5,10,[2,2,6,5,4],[6,3,5,4,6])) print(showRes(5,10,[2,2,6,5,4],valueExcel)) # 输出结果为:[5, 2, 1]
2. 多重背包问题
2.1 问题详解
2.2 题目思路
2.2.1 一般思路
例如,第i种物品有3个,因此可以把这三个物品进行拆分,看作是不同种类的物体,不过是具有相同体积和价值的不同物品,通过拆分,就把可以放多个同种物品拆分成只能放0个或者一个“不同”物品的0-1背包问题。2.2.1 python代码
# weightList:每种物品的体积 # valueList:每种物品的价值 # numList:每种物品的数量 def trans(weightList,valueList,numList): # 转换函数 K = len(numList) newWeightList = [] newValueList = [] num = sum(numList) for i in range(K): for j in range(numList[i]): newWeightList.append(weightList[i]) newValueList.append(valueList[i]) return num,newValueList,newWeightList def zeroOneBag(numList,capacity,weightList,valueList): # 先将多重问题转成0-1问题,利用0-1问题的代码。 num,newValueList,newWeightList = trans(weightList,valueList,numList) valueExcel= [[0 for j in range(capacity + 1)] for i in range(num + 1)] for i in range(1,num+1): for j in range(1,capacity+1): valueExcel[i][j] = valueExcel[i - 1][j] if j >= newWeightList[i-1] and valueExcel[i][j] < (valueExcel[i - 1][j - newWeightList[i - 1]] + newValueList[i - 1]): valueExcel[i][j] = (valueExcel[i - 1][j - newWeightList[i - 1]] + newValueList[i - 1]) return valueExcel print(zeroOneBag([2,5,10],8,[2,2,1],[20,10,6])) # 输出结果: #[[0, 0, 0, 0, 0, 0, 0, 0, 0], # [0, 0, 20, 20, 20, 20, 20, 20, 20], # [0, 0, 20, 20, 40, 40, 40, 40, 40], # [0, 0, 20, 20, 40, 40, 50, 50, 50], # [0, 0, 20, 20, 40, 40, 50, 50, 60], # [0, 0, 20, 20, 40, 40, 50, 50, 60], # [0, 0, 20, 20, 40, 40, 50, 50, 60], # [0, 0, 20, 20, 40, 40, 50, 50, 60], # [0, 6, 20, 26, 40, 46, 50, 56, 60], # [0, 6, 20, 26, 40, 46, 52, 56, 62], # [0, 6, 20, 26, 40, 46, 52, 58, 62], # [0, 6, 20, 26, 40, 46, 52, 58, 64], # [0, 6, 20, 26, 40, 46, 52, 58, 64], # [0, 6, 20, 26, 40, 46, 52, 58, 64], # [0, 6, 20, 26, 40, 46, 52, 58, 64], # [0, 6, 20, 26, 40, 46, 52, 58, 64], # [0, 6, 20, 26, 40, 46, 52, 58, 64], # [0, 6, 20, 26, 40, 46, 52, 58, 64]]
最终的最大价值为64。和0-1背包问题一样,可以对空间进行优化,这里就省略了。
2.2.2 优化
利用一般的思路讲多重背包问题转化成0-1背包问题进行解决,某种物品有多少个就要拆分成多少个不同的物品,这会增加时间复杂度和空间复杂度。因此我们可以利用另一种分解方法:二进制分解
二进制分解代码
def binaryDecomposition(n): # 二进制分解 k = 0 res = [] while n - 2**(k+1) + 1 > 0: res.append(2**k) k += 1 res.append(n-2 ** (k) + 1) return res
如果第i种物品有13个,根据这种思路,13拆分成1,2,4,6。只需要将这种物品拆分成4个物品,这四个物品的体积和价值分别是(Wi,Vi),(2Wi,2Vi),(4Wi,4Vi),(6Wi,6Vi),而不是13个物品,这就降低了时间复杂度和空间复杂度。
2.2.2 python代码
# optimization def binaryDecomposition(n): # 二进制分解 k = 0 res = [] while n - 2**(k+1) + 1 > 0: res.append(2**k) k += 1 res.append(n-2 ** (k) + 1) return res def trans(weightList,valueList,numList): newWeightList = [] newValueList = [] for i in range(len(numList)): for j in binaryDecomposition(numList[i]): newWeightList.append(j * weightList[i]) newValueList.append(j * valueList[i]) num = len(newValueList) return num,newValueList,newWeightList def zeroOneBag(numList,capacity,weightList,valueList): num,newValueList,newWeightList = trans(weightList,valueList,numList) valueExcel= [[0 for j in range(capacity + 1)] for i in range(num + 1)] for i in range(1,num+1): for j in range(1,capacity+1): valueExcel[i][j] = valueExcel[i - 1][j] if j >= newWeightList[i-1] and valueExcel[i][j] < (valueExcel[i - 1][j - newWeightList[i - 1]] + newValueList[i - 1]): valueExcel[i][j] = (valueExcel[i - 1][j - newWeightList[i - 1]] + newValueList[i - 1]) return valueExcel print(zeroOneBag([2,5,10],8,[2,2,1],[20,10,6])) # 输出结果为: [[0, 0, 0, 0, 0, 0, 0, 0, 0], #[0, 0, 20, 20, 20, 20, 20, 20, 20], #[0, 0, 20, 20, 40, 40, 40, 40, 40], #[0, 0, 20, 20, 40, 40, 50, 50, 50], #[0, 0, 20, 20, 40, 40, 50, 50, 60], #[0, 0, 20, 20, 40, 40, 50, 50, 60], #[0, 6, 20, 26, 40, 46, 50, 56, 60], #[0, 6, 20, 26, 40, 46, 52, 58, 62], #[0, 6, 20, 26, 40, 46, 52, 58, 64], #[0, 6, 20, 26, 40, 46, 52, 58, 64]]
通过输出结果也可以看出,表的维度比上一种方法要低。最终的最佳组合的价值为64。
3.完全背包问题
3.1 问题描述
3.2.1 思路
完全背包问题和多重背包问题以及0-1背包问题的唯一不同就在于在背包容量允许的情况下,可以在背包里放无限个同一种物品。
下面是0-1背包问题的递推公式:
我们仍然令V(i,j)表示当前背包为容量 j,前 i 个物品最佳组合对应的价值最优解。那么我们可以根据这个0-1背包问题的状态转换方程通过变化,得到完全背包问题的递推公式。
3.2 python代码
def compKnap(num,capacity,weightList,valueList): valueExcel = [[0 for j in range(capacity + 1)] for i in range(num + 1)] for i in range(1, num + 1): for j in range(1, capacity + 1): for k in range((j // weightList[i - 1]) + 1): if valueExcel[i][j] < (valueExcel[i - 1][j - k*weightList[i - 1]] + k*valueList[i - 1]): valueExcel[i][j] = (valueExcel[i - 1][j - k * weightList[i - 1]] + k*valueList[i - 1]) return valueExcel # print(compKnap(5,16,[5,4,7,2,6],[12,3,10,3,6])) """ 输出结果为: [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 12, 12, 12, 12, 12, 24, 24, 24, 24, 24, 36, 36], [0, 0, 0, 0, 3, 12, 12, 12, 12, 15, 24, 24, 24, 24, 27, 36, 36], [0, 0, 0, 0, 3, 12, 12, 12, 12, 15, 24, 24, 24, 24, 27, 36, 36], [0, 0, 3, 3, 6, 12, 12, 15, 15, 18, 24, 24, 27, 27, 30, 36, 36], [0, 0, 3, 3, 6, 12, 12, 15, 15, 18, 24, 24, 27, 27, 30, 36, 36]] """
3.2.2 优化
和0-1背包问题一样,完全背包问题也可以通过二进制分解来进行拆分,来降低时间复杂度和空间复杂度。同时,还可以优化,将其优化成和相同条件下0-1背包问题时间复杂度、空间复杂度一样的算法。
其方法和0-1背包问题的优化方法一样。都是借助一个一维数组。3.2.2 python 代码
def compKnapOpt(num,capacity,weightList,valueList): valueExcel = [0 for j in range(capacity + 1)] for i in range(1, num + 1): for j in range(1, capacity + 1): if weightList[i-1]<=j: valueExcel[j] = max(valueExcel[j - weightList[i - 1]] + valueList[i - 1], valueExcel[j]) return valueExcel print(compKnapOpt(5,16,[5,4,7,2,6],[12,3,10,3,6])) # 输出结果: [0, 0, 3, 3, 6, 12, 12, 15, 15, 18, 24, 24, 27, 27, 30, 36, 36]
- 建立模型,我们要求在物品总体积限制为capacity的情况下,尽可能装下价值高的物品组合,其模型如下:
-
二维背包动态规划问题——两个约束
2020-12-08 10:09:16由于涉及三维度的优化问题,此篇主要记录单个区域调度最优情况,类比二维背包问题,两个约束,dp初始化为成本最大值,放入小哥的value为小哥的节约成本,并打印出分配结果。 import pandas as pd import json ... -
01背包问题 java
2017-03-12 21:00:5001背包问题 编辑 基本概念 01背包是背包问题中最简单的问题。01背包的约束条件是给定几种物品,每种物品有且只有一个,并且有权值和体积两个属性。在01背包问题中,因为每种物品只有一个,对于每个... -
背包问题(一)---------0_1背包问题
2018-09-01 08:06:56背包问题有多种,比如: ...问题3:多背包问题,m个背包,背包j装入最大重量Bj,j=1、2、3........m,在满足所有背包重量约束 条件下使得装入物品价值最大 问题4:二维背包,每件物品有wi和体积ti,i=1,2......... -
背包问题---接触动态规划
2020-06-02 15:37:21-接触动态规划动态规划的理解0-1背包问题题目基本思路优化空间一个常数优化空间初始化问题完全背包问题题目基本思路简单的优化方法转为0-1背包多重背包问题题目基本算法转为0-1背包问题二维背包问题--多条件约束问题... -
论文研究-贪心粒子群算法求解多维0-1背包问题 .pdf
2019-08-20 17:40:07贪心粒子群算法求解多维0-1背包问题,郝俊玲,,本文将单维背包问题求解中常用的贪心思想推广到多维0-1背包问题,但多维背包问题的多约束特性使得单维背包问题中按物品性价比非增 -
背包问题(1)-------01背包
2019-05-28 15:26:00首先,我也是才晓得01背包,以前觉得是个比较高升的问题,但是现在就感觉还好,难度较小,理解起来比较容易,是背包问题中最简单的问题,多说无益,先来看一看,01背包的概念 01背包是在M件物品取出若干件放在空间... -
论文研究 - 一类连续可分离的非线性多维背包问题
2020-05-27 07:38:33非线性多维背包问题定义为具有多个线性约束的凸函数的最小化。 为非线性多维规划问题开发的方法通常用于解决非线性多维背包问题,但是由于大多数方法都没有利用背包问题的特征,因此它们的效率低下或受到限制。 本文... -
优先队列式分支限界法_0-1背包问题
2020-05-29 00:02:190-1背包问题中,物品i在考虑是否装入背包时只有两种选择,即要么全部装入背包,要么全部不装入背包,不能只装入物品i的一部分,也不能将物品i装入背包多次。此问题的形式化描述是:给定 ,要求找出n元0-1向量 , , ,... -
分支限界法解决0-1背包问题
2020-05-27 20:56:340-1背包问题我们已经说过很多次了,这次是用最近学的分支限界法解决。分支限界法就是利用队列或者优先队列在储存解空间树的活结点,并每次弹出一个作为扩展结点,是一种广度优先遍历,区别于回溯法的深度优先遍历。... -
c语言让多重循环时间复杂度降低_第一节 背包问题三大模型&代码(0-1背包/完全背包/多重背包)...
2020-12-05 12:08:49写在前面 最近参与了导师... 去网上找了找相关的背包问题教学视频和一些文献,相关文献的研究当然更加站在学术前沿一点,但是万变不离其宗,所以,根据网上的一些教学视频,总结了一个背包问题的几大基础模型的笔记... -
经典遗传算法(SGA)解01背包问题的原理及其python(python3.6)代码实现
2018-10-25 21:40:171.背包问题 背包问题(knapsack problem)是指从多种物品(项目)中选择几件物品转满背包。...1.1简单约束的背包问题 背包问题是理论上的NP-Hard问题,目前还没有可求最优解的多项式时间算法。但很多情况... -
回溯法解决0/1背包问题(c++)
2020-11-23 16:41:30用回溯法解决0-1背包问题时,其解空间有长度为n的0-1向量组成,并可以组织成高度为n+1满二叉树。二叉树的结点按层次遍历的顺序从上到下、从左到右的顺序编号(从1开始)。 采用回溯法解决问题时,可以使用约束条件对... -
用回溯法解决0-1背包问题
2016-04-27 19:02:22用回溯法解决0-1背包问题需要解决一下问题: 1.如何动态生成子集树 2.如何设计子集树中的结点类型 3.如何设计两个剪枝函数:约束函数和限界函数 4.如何保存一个或多个最优解,同时保存最优值 解决方法: 1.... -
0-1背包问题(5种方法)
2021-01-15 15:26:39有n件物品要装入背包,第i件物品的重量wi,价值vi,i=1,2,…,n,背包最多允许装入的重量为B,问如何选择装入背包的物品,使得总价值达到最大? 穷举法 解是一个取值只能是0或1的向量,最先考虑考虑的是穷举,... -
背包问题02--其实一切都没那么难
2016-07-06 02:07:00{之前听过同学说面试华为的题目,也是背包问题。大概是这样。有一对东西的集合,他们分别有不同的重量,然后又两个包,需要你把东西分成两份,约束条件是:两个包的差别需要是最小。当时一听这题都懵b了。但是这个... -
0-1背包问题实现(python)和Palindrome Partitioning II的完成
2019-01-09 21:51:2901背包问题 一. 问题描述 有n 个物品,它们有各自的重量和价值,现有给定容量的背包,如何让背包里装入的物品具有最大的价值总和?(人话就是:一个小偷去商店偷东西,但是由于带来的袋子不够大,装不完所有的东西,... -
回溯法,并用回溯法请求0/1背包问题和皇后问题
2016-12-18 12:31:11在用穷举法求解的过程中,很多候选的解可以在求解中途被约束条件淘汰点,从而降低求解的复杂度。基于这种思想引出了回溯法。 回溯法是穷举法的一个改进,因为它也是一种通用的算法。一个问题可能会有多种可能解... -
【动态规划】二维费用的背包问题
2020-03-21 15:07:31多了一层约束条件,所有又多了一层循环。 #include <iostream> using namespace std; const int maxn=1e2+10; int v,m,w,dp[maxn][maxn]; int M,n,V; int main(){ cin>>n>>V>>M; for(int ... -
01背包
2017-04-12 21:08:1601背包是背包问题中最简单的问题。01背包的约束条件是给定几种物品,每种物品有且只有一个,并且有权值和体积两个属性。在01背包问题中,因为每种物品只有一个,对于每个物品只需要考虑选与不选两种情况。如果不选择... -
基于动态背包的多场景广告序列投放算法
2020-08-17 11:57:27简介:电商广告是广告主接触其目标用户的重要手段。...为求解此背包问题,我们提出了一个具有理论保证的双层优化框架,该框架在不影响求解精度同时,显着减少了原始优化问题的求解空间。在下层框架的优化中,我们 -
[HDU3535] [2010多校联考10] AreYouBusy [分组背包][01背包]
2018-10-31 19:20:12第三种不带约束的很简单,01背包就可以了。 其它两种分别是两类分组背包。 需要注意的是ci, gi≥0。注意为0的情况,不要重复计算。 三个子问题都是经典的,尤其是两个分组背包如果没有做过应该了解一下。 其中有... -
智能算法 | 遗传算法 处理 服务器资源分配问题
2018-05-12 14:36:50问题描述:给出一定用户的...若单单解决该问题,则dp是最佳的选择,由于题目后期会有拓展(多维度多约束背包问题),并且有时间上的要求,考虑到这个原因,我就放弃了dp。个人觉得蚁群的复杂度较高,所以也放弃了蚁... -
2020ccpc 威海 Clock Master(多个数的lcm+分组背包)
2020-10-27 21:28:14+ a[ m ] = n,( m 没有约束 ),使得 lcm( a[ 0 ] , a[ 1 ] , ... a[ m ] ) 最大,输出这个最大值的对数 思路:将n分解成m个数之后,问题就变成了如何求m个数的lcm。有一种做法是用gcd(a,b)*lcm(a,b)==a*b。但是将... -
nsga2中如何添加约束条件
2019-05-07 17:02:51本人使用nsga2解决多目标0-1背包问题 对于如何添加约束条件不清楚 约束如图 希望得到帮助 本人所用语言为matlab