动态规划解决0-1背包问题详解(图文并茂)
动态规划解决0-1背包问题这个是网上比较好的案例,因为原文有些地方晦涩难懂,对于刚接触动态规划问题的朋友来说很不友好,所以很对地方加入了我自己的见解,也是作为我的一次学习历程。一、问题描述:有n 个物品,它们有各自的重量和价值,现有给定容量的背包,如何让背包里装入的物品具有最大的价值总和?二、总体思路:根据动态规划解题步骤(问题抽象化、建立模型、寻找约束条件、判断是否满足最优性原理、找大...
动态规划解决0-1背包问题
这个是网上比较好的案例,因为原文有些地方晦涩难懂,对于刚接触动态规划问题的朋友来说很不友好,所以很对地方加入了我自己的见解,也是作为我的一次学习历程。
一、问题描述:
有n 个物品,它们有各自的重量和价值,现有给定容量的背包,如何让背包里装入的物品具有最大的价值总和?
二、总体思路:
根据动态规划解题步骤(问题抽象化、建立模型、寻找约束条件、判断是否满足最优性原理、找大问题与小问题的递推关系式、填表、寻找解组成)找出0-1背包问题的最优解以及解组成,然后编写代码实现;
三、动态规划的原理及过程:
一个案例:有4个物品,其体积w={2,3,4,5},其价值依次为v={3,4,5,6},背包的容量为8。如何将物品装入背包使得其总价值最大?
1、原理
动态规划与分治法类似,都是把大问题拆分成小问题,通过寻找大问题与小问题的递推关系,解决一个个小问题,最终达到解决原问题的效果。但不同的是,分治法在子问题和子子问题等上被重复计算了很多次(即重叠子问题),而动态规划则具有记忆性,通过填写表把所有已经解决的子问题答案纪录下来,在新问题里需要用到的子问题可以直接提取,避免了重复计算,从而节约了时间,所以在问题满足最优性原理之后,用动态规划解决问题的核心就在于填表,表填写完毕,最优解也就找到。
动态规划步骤
1)找出最优解的性质,并刻画其结构特征
2)递归的定义最优值
3)以自第向上的方式计算出最优值
4)根据计算最优值时得到的信息,构造一个最优解
2、过程
a) 把背包问题抽象化(X1,X2,…,Xn,其中 Xi 取0或1,表示第 i 个物品选或不选),Vi表示第 i 个物品的价值,Wi表示第 i 个物品的体积(重量);
b) 建立模型,即求max(V1X1+V2X2+…+VnXn);
c) 约束条件,W1X1+W2X2+…+WnXn<capacity;
d) 定义V(i,j):当前背包容量 j,前 i 个物品最佳组合对应的价值;
e) 最优性原理是动态规划的基础,最优性原理是指“多阶段决策过程的最优决策序列具有这样的性质:不论初始状态和初始决策如何,对于前面决策所造成的某一状态而言,其后各阶段的决策序列必须构成最优策略”。判断该问题是否满足最优性原理,采用反证法证明:
假设(X1,X2,…,Xn)是0-1背包问题的最优解,则有(X2,X3,…,Xn)是其子问题的最优解,
假设(Y2,Y3,…,Yn)是上述问题的子问题最优解,则理应有(V2Y2+V3Y3+…+VnYn)+V1X1 > (V2X2+V3X3+…+VnXn)+V1X1;
而(V2X2+V3X3+…+VnXn)+V1X1=(V1X1+V2X2+…+VnXn),则有(V2Y2+V3Y3+…+VnYn)+V1X1 > (V1X1+V2X2+…+VnXn);
该式子说明(X1,Y2,Y3,…,Yn)才是该0-1背包问题的最优解,这与最开始的假设(X1,X2,…,Xn)是01背包问题的最优解相矛盾,故0-1背包问题满足最优性原理;
f) 寻找递推关系式,面对当前商品有两种可能性:
第一,包的剩余容量比该商品体积小,装不下,此时的价值与前i-1个的价值是一样的,即V(i,j)=V(i-1,j);
第二,还有足够的容量可以装该商品,但装了也不一定达到当前最优价值,所以在装与不装之间选择最优的一个,即V(i,j)=max{ V(i-1,j),V(i-1,j-w(i))+v(i) };其中V(i-1,j)表示不装第i号物品的价值,V(i-1,j-w(i))+v(i) 表示装了第i个商品,背包容量减少w(i)但价值增加了v(i);
由此可以得出递推关系式:(i是物品编号,j是背包剩余容量)
1) j<w(i) V(i,j)=V(i-1,j)
2) j>=w(i) V(i,j)=max{ V(i-1,j),V(i-1,j-w(i))+v(i) }注意:大写V(i-1,j-w(i))表示可装入背包中的在背包容量为j-w(i)前提下,前(i-1)个商品的最大总价值,小写v(i)表示第i个商品的价值。
g) 填表,首先初始化边界条件,V(0,j)=V(i,0)=0;(解析:结合下图分析,V(0,j)表示物品是 0,即背包中不放入任何物品,所以背包的价值为0;V(i,0)表示背包的容量为0,所以背包中放不下任何物品,所以其价值也为0,所以第一行和第一列均为0!)
h) 然后一行一行的填表
1) 如:i=1,j=1,w(1)=2,v(1)=3,(即当背包容量为1的情况下,1号物品能能否放入背包)因为j=1,w(1)=2,j < w(1),故物品1不能放进背包,所以V(1,1)=V(1-1,1)=0;
2) 又如i=1,j=2,w(1)=2,v(1)=3,(即在容量为2的情况下,1号物品能否放入背包)因为j=2, w(1)=2,j=w(1),故V(1,2)=max{ V(1-1,2),V(1-1,2-w(1))+v(1) }=max{0,0+3}=3(放入1号物品的价值是3,不放入1号物品的价值是0,选择价值大的操作);
3) 如此下去,填到最后一个,i=4,j=8,w(4)=5,v(4)=6,有j>w(4),故V(4,8)=max{ V(4-1,8),V(4-1,8-w(4))+v(4) }=max{9,4+6}=10(如果装入物品4,则在剩余背包容量中(8-5=3)中选取1、2、3号物品装入可获得最大价值的组合+当前物品的价值与不放入该物品的最大价值相比较,取最大的即可)。所以填完表如下图:
void FindMax()//动态规划
{
int i,j;
//填表
for(i=1;i<=number;i++)
{
for(j=1;j<=capacity;j++)
{
if(j<w[i])//包装不进
{
V[i][j]=V[i-1][j];
}
else//能装
{
if(V[i-1][j]>V[i-1][j-w[i]]+v[i]) //不装价值大
{
V[i][j]=V[i-1][j];
}
else//前i-1个物品的最优解与第i个物品的价值之和更大
{
V[i][j]=V[i-1][j-w[i]]+v[i];
}
}
}
}
}
i) 表格填完,最优解即是V(number,capacity)=V(4,8)=10,但还不知道解由哪些商品组成,故要根据最优解自底向上找出解的组成,根据填表的原理可以有如下的寻解方式:
1) V(i,j)=V(i-1,j)时,说明没有选择第i 个商品,即在背包容量为j的情况下,前i个商品的最优值与前(i-1)个商品的最优值相同,则回到V(i-1,j);
2) V(i,j)=V(i-1,j-w(i))+v(i)时,说明装了第i个商品,该商品是最优解组成的一部分,随后我们得回到装该商品之前,即回到V(i-1,j-w(i));
3) 一直遍历到i=0结束为止,所有解的组成都会找到。
j) 根据我们举的案例,我们从价值最大的10开始自底向上查找都是哪些物品装入了背包:
1) 最优解为V(4,8)=10,而V(4,8)!=V(3,8)却有V(4,8)=V(3,8-w(4))+v(4)=V(3,3)+6=4+6=10,所以第4件商品被选中,并且回到V(3,8-w(4))=V(3,3);
2) 有V(3,3)=V(2,3)=4,所以第3件商品没被选择,回到V(2,3);
3) 而V(2,3)!=V(1,3)却有V(2,3)=V(1,3-w(2))+v(2)=V(1,0)+4=0+4=4,所以第2件商品被选中,并且回到V(1,3-w(2))=V(1,0);
4) 有V(1,0)=V(0,0)=0,所以第1件商品没被选择;
k) 到此,0-1背包问题已经解决,利用动态规划解决此问题的效率即是填写此张表的效率,所以动态规划的时间效率为O(numbercapacity)=O(nc),由于用到二维数组存储子问题的解,所以动态规划的空间效率为O(n*c);
查找解的最优组成
void FindWhat(int i,int j)//寻找解的组成方式
{
if(i>=0)
{
if(V[i][j]==V[i-1][j]) //相等说明没装
{
item[i]=0; //全局变量,标记未被选中
FindWhat(i-1,j);
}
else if( j-w[i]>=0 && V[i][j]==V[i-1][j-w[i]]+v[i] )
{
item[i]=1;//标记已被选中
FindWhat(i-1,j-w[i]);//回到装包之前的位置
}
}
}
![Logo](https://devpress.csdnimg.cn/79de2bf0b7994defa4242ef90d5513fa.jpg)
开放原子开发者工作坊旨在鼓励更多人参与开源活动,与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动,如meetup、训练营等,主打技术交流,干货满满,真诚地邀请各位开发者共同参与!
更多推荐
所有评论(0)