2023年7月31日发(作者：)
动态规划算法解01背包问题（思路及算法实现）说明：算法源⾃教材。本⽂相当于对教材做的⼀个笔记(动态规划与贪⼼算法解01背包必须先对背包按照单位重量的价格从⼤到⼩排序，否则拆分的⼦问题就不具备最优⼦结构的性质)动态规划算法： 动态规划就是⼀个填表的过程。该表记录了已解决的⼦问题的答案。求解下⼀个⼦问题时会⽤到上⼀个⼦问题的答案。{⽐如01背包问题：假如有1个背包，背包容量是10，有5个物品，编号为1，2，3，4，5，他们都有各⾃的重量和价格。要求在不超过背包容量的情况下，使背包装载物品的价值最⼤。现将问题拆分为五个⼦问题。1.背容=10，从1号物品中找出该问题的解2.背容=10，从1号，2号物品中找出该问题的解3.背容=10，从1号，2号，3号物品中找出该问题的解4.背容=10，从1号，2号，3号，4号物品中找出该问题的解5.背容=10，从1号，2号，3号，4号，5号物品中找出该问题的解}思路： 我们可以将1，2，3，4，5⼦问题的答案都存⼊⼀张表中。因为求解2⼦问题，需要⽤到1⼦问题的答案(2的每⼀步⽅案要与1的每⼀步⽅案⽐较，如何2的该步⽅案优于1所对应的⽅案。则将2的这步⽅案标为可⾏。如果不优于1的，或者不满⾜问题的约束条件，则舍弃该⽅案。继续沿⽤该步所对应的1的⽅案作为该步的⽅案)。求解3⼦问题，需要⽤到2⼦问题的答案，⼀直递推到求解5⼦问题，需要⽤到4⼦问题的答案。⽽5⼦问题就是原问题。5⼦问题的答案就是最终原问题的解。
解法： 以01背包问题为例，作讲解。给出问题参数： c=10; //背包容量c n=5; //物体个数n int w[6]={0,2,2,6,5,4}; //物重w,0⽆意义，只是为⽅便描述问题⽽已 int p[6]={0,6,3,5,4,6}; //物价p
运⾏的最终结果是张⼆维表：（f[i][j],i就是n，j就是c）nc6663959141415填表相关说明：1.程序是⼀⾏⼀⾏的进⾏填表的。f[0][0,1,2,]......f[5][0,1,2,] (程序初始化的过程就是将第0⾏的所有数填为0，这是符合现实情况的。它表明当前背包没有装物品，当前背包的价值是0)2.拿f[3][8]=11来说明填表的过程。f[3]表明i=3(当前⼦问题有3个物品可选，分别是1，2，3号物品)，f[3][*]的值就是第3个⼦问题的解。我要选的3号物品的重量是6，它的价值是5，所以我会找到它的前6列的上⼀⾏所对应的背包的价值（f[2][2]）+5（当前要选的3号物品的价值）=11,值为11>f[2][8]=9，代表我选了1,3的⽅案要优于选1，2的这种⽅案，所以我将11填⼊到表格【如果f[2][2]+5<9,则将9填⼊表格】-------------------这⾥需要说明⼀下f[2][8]=9的含义：2⼦问题的⼀个解是{1，2}选择1，2号物品所对应的背包价值为9。------恰巧我们在解决3⼦问题时{1，2，3}需要计算⽐较这⼏种⽅案，选1，2号物品{1，2}>>>>背价=？，背包价格是多少，{1，3}>>>>背价=？,{1，2,3}>>>>背价=？⽽{1,2}>>背包价格在2⼦问题中已给出，因此我们可以在3⼦问题中直接⽤。为何不考虑{2，3}呢？就是拿2号和3号组队放⼊背包？因为在2⼦问题中已经记载了：【如果要单选⼀个背包的话，选择1号获得的价值要⽐2号获得的价值⼤----我们追溯到f[2][2]=6是整么来的，背包容量是2的时候，[1,2]号物品只能有⼀个放⼊背包，放⼊1，背包的价值是6，f[1][2]=6的计算是在1⼦问题中已经求解出来的，2⼦问题可以直接⽤该值，⽽不⽤再重复计算。放⼊2号，背值是3，3<6,所以沿⽤上⼀个⼦问题的解作为该步的答案，所以f[2][2]是6，⽽不是3，所以它相当于定义说：下⼀个⼦问题在求解的过程中，如果遇到只能从2号和1号物品中选择⼀个物品装⼊背包时，请选择1号物品】3.其实将上述的描述写成代码，就是两层for循环（遍历n，再嵌套遍历c），加上两个判断（1.当前⼦问题的可⾏的⼀个⽅案与上⼀个⼦问题的对应的可⾏⽅案谁最优。2.连续变量j的值是否达到了跳跃点的值，达到了才更新当前背包的价值）：代码如下#include
cout<<"背包能装的最⼤价值是：" << f[i-1][j-1] < /* int w[100]; int p[100]; cout << "请输⼊背包容量c："<< endl; cin >>c; cout <<"请输⼊物体个数n："< { cout<<"请输⼊物重w["< } for(int i=1;i<=n;i++) { cout<<"请输⼊物价p["< c=10; //背包容量c n=5; //物体个数n int w[6]={0,2,2,6,5,4}; //物重w int p[6]={0,6,3,5,4,6}; //物价p Knapsack(n,c,w,p); }如何进⼀步优化算法： 上述算法有两个明显的缺点: 其⼀是算法要求所给物品的重量w[i]是整数. 其次，当背包容量很⼤时，算法需要的计算时间较多，当c>2^n,算法需要n*2^n这么多的计算时间. 优化思路： 仔细观察，发现该⼆维表的值，是关于物品背包当前背包容量的阶梯状函数，并且它是⼀个阶梯状，单调不减函数，所以我们可以通过构造跳跃点集的⽅式来优化算法。其相关说明如下：程序运⾏的数据流图如下：最后放⼀下优化后的算法的代码实现：#include
2023年7月31日发(作者：)
动态规划算法解01背包问题（思路及算法实现）说明：算法源⾃教材。本⽂相当于对教材做的⼀个笔记(动态规划与贪⼼算法解01背包必须先对背包按照单位重量的价格从⼤到⼩排序，否则拆分的⼦问题就不具备最优⼦结构的性质)动态规划算法： 动态规划就是⼀个填表的过程。该表记录了已解决的⼦问题的答案。求解下⼀个⼦问题时会⽤到上⼀个⼦问题的答案。{⽐如01背包问题：假如有1个背包，背包容量是10，有5个物品，编号为1，2，3，4，5，他们都有各⾃的重量和价格。要求在不超过背包容量的情况下，使背包装载物品的价值最⼤。现将问题拆分为五个⼦问题。1.背容=10，从1号物品中找出该问题的解2.背容=10，从1号，2号物品中找出该问题的解3.背容=10，从1号，2号，3号物品中找出该问题的解4.背容=10，从1号，2号，3号，4号物品中找出该问题的解5.背容=10，从1号，2号，3号，4号，5号物品中找出该问题的解}思路： 我们可以将1，2，3，4，5⼦问题的答案都存⼊⼀张表中。因为求解2⼦问题，需要⽤到1⼦问题的答案(2的每⼀步⽅案要与1的每⼀步⽅案⽐较，如何2的该步⽅案优于1所对应的⽅案。则将2的这步⽅案标为可⾏。如果不优于1的，或者不满⾜问题的约束条件，则舍弃该⽅案。继续沿⽤该步所对应的1的⽅案作为该步的⽅案)。求解3⼦问题，需要⽤到2⼦问题的答案，⼀直递推到求解5⼦问题，需要⽤到4⼦问题的答案。⽽5⼦问题就是原问题。5⼦问题的答案就是最终原问题的解。
解法： 以01背包问题为例，作讲解。给出问题参数： c=10; //背包容量c n=5; //物体个数n int w[6]={0,2,2,6,5,4}; //物重w,0⽆意义，只是为⽅便描述问题⽽已 int p[6]={0,6,3,5,4,6}; //物价p
运⾏的最终结果是张⼆维表：（f[i][j],i就是n，j就是c）nc6663959141415填表相关说明：1.程序是⼀⾏⼀⾏的进⾏填表的。f[0][0,1,2,]......f[5][0,1,2,] (程序初始化的过程就是将第0⾏的所有数填为0，这是符合现实情况的。它表明当前背包没有装物品，当前背包的价值是0)2.拿f[3][8]=11来说明填表的过程。f[3]表明i=3(当前⼦问题有3个物品可选，分别是1，2，3号物品)，f[3][*]的值就是第3个⼦问题的解。我要选的3号物品的重量是6，它的价值是5，所以我会找到它的前6列的上⼀⾏所对应的背包的价值（f[2][2]）+5（当前要选的3号物品的价值）=11,值为11>f[2][8]=9，代表我选了1,3的⽅案要优于选1，2的这种⽅案，所以我将11填⼊到表格【如果f[2][2]+5<9,则将9填⼊表格】-------------------这⾥需要说明⼀下f[2][8]=9的含义：2⼦问题的⼀个解是{1，2}选择1，2号物品所对应的背包价值为9。------恰巧我们在解决3⼦问题时{1，2，3}需要计算⽐较这⼏种⽅案，选1，2号物品{1，2}>>>>背价=？，背包价格是多少，{1，3}>>>>背价=？,{1，2,3}>>>>背价=？⽽{1,2}>>背包价格在2⼦问题中已给出，因此我们可以在3⼦问题中直接⽤。为何不考虑{2，3}呢？就是拿2号和3号组队放⼊背包？因为在2⼦问题中已经记载了：【如果要单选⼀个背包的话，选择1号获得的价值要⽐2号获得的价值⼤----我们追溯到f[2][2]=6是整么来的，背包容量是2的时候，[1,2]号物品只能有⼀个放⼊背包，放⼊1，背包的价值是6，f[1][2]=6的计算是在1⼦问题中已经求解出来的，2⼦问题可以直接⽤该值，⽽不⽤再重复计算。放⼊2号，背值是3，3<6,所以沿⽤上⼀个⼦问题的解作为该步的答案，所以f[2][2]是6，⽽不是3，所以它相当于定义说：下⼀个⼦问题在求解的过程中，如果遇到只能从2号和1号物品中选择⼀个物品装⼊背包时，请选择1号物品】3.其实将上述的描述写成代码，就是两层for循环（遍历n，再嵌套遍历c），加上两个判断（1.当前⼦问题的可⾏的⼀个⽅案与上⼀个⼦问题的对应的可⾏⽅案谁最优。2.连续变量j的值是否达到了跳跃点的值，达到了才更新当前背包的价值）：代码如下#include
cout<<"背包能装的最⼤价值是：" << f[i-1][j-1] < /* int w[100]; int p[100]; cout << "请输⼊背包容量c："<< endl; cin >>c; cout <<"请输⼊物体个数n："< { cout<<"请输⼊物重w["< } for(int i=1;i<=n;i++) { cout<<"请输⼊物价p["< c=10; //背包容量c n=5; //物体个数n int w[6]={0,2,2,6,5,4}; //物重w int p[6]={0,6,3,5,4,6}; //物价p Knapsack(n,c,w,p); }如何进⼀步优化算法： 上述算法有两个明显的缺点: 其⼀是算法要求所给物品的重量w[i]是整数. 其次，当背包容量很⼤时，算法需要的计算时间较多，当c>2^n,算法需要n*2^n这么多的计算时间. 优化思路： 仔细观察，发现该⼆维表的值，是关于物品背包当前背包容量的阶梯状函数，并且它是⼀个阶梯状，单调不减函数，所以我们可以通过构造跳跃点集的⽅式来优化算法。其相关说明如下：程序运⾏的数据流图如下：最后放⼀下优化后的算法的代码实现：#include
发布评论