本文为网上复制
网上各大公司经常出题目:假设现在有1元、2元、5元的纸币很多张,现在需要20块钱,你能给多少种找钱方案,这就可以认为是完全背包问题,即背包容量为20,物品体积分别为1、2、5。
还有公司出题目:给定一个数m,将m拆成不同的自然数的和的形式有多少种方案,这就是典型的01背包问题,背包容量为m,物品件数为k,这里面的k是隐含条件,可以求出来,因为m最多由1+2+…+k得到,由此可以根据m求得物品件数的上限。
现在切入正题,我们先谈“01背包”将背包刚好装满的方案总数。“完全背包”和“01背包”极为相似,只有极少量代码变动。
01背包装满的问题抽象化:
设背包容量为V,一共N件物品,每件物品体积为C[i],每件物品的价值为W[i],求将背包装满的方案总数。
1) 子问题定义:F[i][j]表示前i件物品中选取若干件物品放入剩余空间为j的背包中刚好把背包装满的方案总数。
2) 根据第i件物品体积和所剩背包容量大小进行决策
(1-1)
注意初始化条件为F[0][0]=1,即没有物品放入容量为0的背包刚好放满的方案数为1。
故可得伪代码如下:
-
F[0][0]←1
-
-
fori←1toN
-
-
doforj←0toV
-
-
if(j<C[i])
-
-
thenF[i][j]←F[i-1][j]
-
-
else
-
-
F[i][j]←F[i-1][j]+F[i-1][j-C[i]]
-
-
returnF[N][V]
F[0][0] ← 1 for i ← 1 to N do for j ← 0 to V if (j < C[i]) then F[i][j] ← F[i-1][j] else F[i][j] ← F[i-1][j]+F[i-1][j-C[i]] return F[N][V]
上述代码的空间复杂度为O(NV),由状态方程可知,F[i][]只与F[i-1][]的状态有关,故可以用一维数组来代替二维数组,以降低空间复杂度为O(V)。
降低空间复杂度为O(V)的伪代码如下:
-
F[0]←1
-
-
fori←1toN
-
-
doforj←VtoC[i]
-
-
if(j>=C[i])
-
-
thenF[j]←F[j]+F[j-C[i]]
-
-
returnF[V]
F[0] ← 1 for i ← 1 to N do for j ← V to C[i] if (j >= C[i]) then F[j] ← F[j]+F[j-C[i]] return F[V]
注意对V的遍历变为逆序,至于为什么这样,请看本人博文《背包问题——“01背包”详解及实现(包含背包中具体物品的求解)》。
接下来看看“完全背包”到底有哪些变化。看过《背包九讲》或者本人博文《背包问题——“完全背包”详解及实现(包含背包具体物品的求解)》的读者应该会能很快想到状态方程的变形,如下:
(1-2)
不错,状态方程是这样。F[i-1][j]表示背包中不含第i种物品时把背包装满的方案,F[i][j-C[i]]表示至少包含一件第i种物品把背包装满的方案总数。所以,当j<C[i]时F[i][j] = F[i-1][j];当j >= C[i]时, F[i][j] = F[i][j-C[i]] + F[i-1][j],为什么是两者的和,因为F[i][j-C[i]]和F[i-1][j]都是[i][j]状态时把背包装满的方案,且两者互斥。
伪代码如下:
-
F[0][0]←1
-
-
fori←1toN
-
-
doforj←0toV
-
-
if(j<C[i])
-
-
thenF[i][j]←F[i-1][j]
-
-
else
-
-
F[i][j]←F[i-1][j]+F[i][j-C[i]]
-
-
returnF[N][V]
F[0][0] ← 1 for i ← 1 to N do for j ← 0 to V if (j < C[i]) then F[i][j] ← F[i-1][j] else F[i][j] ← F[i-1][j]+F[i][j-C[i]] return F[N][V]
同样上述伪代码的空间复杂度为O(NV),我们也可以通过用一维数组来降低空间复杂度为O(V)。
伪代码如下:
-
F[0]←1
-
-
fori←1toN
-
-
doforj←C[i]toV
-
-
if(j>=C[i])
-
-
thenF[j]←F[j]+F[j-C[i]]
-
-
returnF[V]
F[0] ← 1for i ← 1 to N do for j ← C[i] to V if (j >= C[i]) then F[j] ← F[j]+F[j-C[i]] return F[V]
相关推荐
背包之01背包、完全背包、多重背包详解.
01背包问题属于组合优化问题的一个例子,求解01背包问题的过程可以被视作在很多可行解当中求解一个最优解。01背包问题的一般描述如下: 给定n个物品和一个背包,物品i的重量为Wi,其价值为Vi,背包的容量为C。选择...
01背包问题是一个很经典的问题,在这里我用回溯法解决。希望大家一起来探讨呀!
简写01背包,用代码实现01背包的具体例子,比较容易理解
背包问题详解 01背包,完全背包,多重背包,混合背包,二维费用背包,分级背包,泛化物品等等的分析思路,解题技巧,还有各种背包问题的题目解答。
背包问题九讲(包含01背包,多重背包,完全背包等)
C语言实现01背包问题 简洁高效 代码都有注释 问题描述: 给定 n 件物品,物品的重量为 w[i],物品的价值为 c[i]。现挑选物品放入背包中,假定背包能承受的最大重量为 V,问应该如何选择装入背包中的物品,使得装入...
实验目的:0/1背包问题的回溯算法设计 实验原理:回溯算法设计。 实验要求:基本掌握回溯算法设计的原理方法。熟练掌握VC++中编程实现算法的常用技术和方法。 算法思想: 0-1背包问题:给定n种物品和一背包.物品i的...
很简单的算法 01背包用C++实现 01.cpp
贪婪法解决01背包问题贪婪法解决01背包问题贪婪法解决01背包问题贪婪法解决01背包问题
计算机学科作业,回溯法实现01背包问题JAVA版.txt
贪心算法 动态规划 分支限界 回溯 四种算法实现01 背包问题 ,有可视化界面和算法的过程描述
C++动态规划实现01背包算法入门通过二维表的方式实现01背包的选取问题
利用动态规划算法实现了01背包问题,并取得了良好的效果。
回溯法解决01背包问题c语言.rar 已调通
01背包问题属于组合优化问题的一个例子,求解01背包问题的过程可以被视作在很多可行解当中求解一个最优解。01背包问题的一般描述如下: 给定n个物品和一个背包,物品i的重量为Wi,其价值为Vi,背包的容量为C。选择...
01背包问题真正的c语言回溯法实现,我在自己试验过的
算法分析与设计-实验三 01背包实验报告
课程作业,实现算法实践书后的例题,实现01背包问题
01背包动态规划,01背包回溯算法,分枝限界法01背包,蛮力法,贪心法,多个背包问题总汇......,好不容易得到的资源