背包问题(下) | 动态规划与MATLAB程序实现
Building可视库
一起做些更酷的事吧！
关注
上次，我们用贪心算法解决了0-1背包问题, 但有着不可避免的缺点，即很难真正找到最优解, 纵使能找出较优的解也往往与真正的最优解相差一定范围。本期采用动态规划算法, 则可解决上述缺点，先介绍完全背包，再介绍0-1背包的求解。
动态规划的思想是将一个规模较大的问题分解成规模相对足够小的子问题，再对子问题求解，然后由这些子问题的解得到原问题的解。它的优势在于它将每一个子问题计算得到的解都保存起来，用到的时候直接调用，节省了大量重复计算时间。
完全背包问题
有编号分别为a，b，c，d，e 的五件物品，（假设每类物品可以装多个）,它们的重量分别是 2，2，6，5，4，它们的价值分别是 6，3，5，4，6，现在给你个承重为10的背包，如何让背包里装入的物品具有最大的价值总和？
根据求解动态规划问题的步骤，一步一步来。用 ci 表示各物品的重量，vi 表示各物品的价值。
首先我们写出线性规划模型：
01--阶段，考虑到要检查5个物品是否装入背包，即分为5个阶段。
02--决策变量，表示第 i 个物品装入几个。
03--状态变量，表示在检查第i个物品时，包中的剩余承重量。
04--状态转移方程，表示相邻状态变量的转换。
05--阶段指标函数，表示第i阶段装入物品的价值
06--最优收益函数，表示检查第 i 个物品时，当包中剩余承重为Si，包中装入物品从i, i+1, ... 5能达到的最大价值。
递推方程如下：
最终结果如下表，整个过程要结合递推方程，采用逆推法，从i=5求解共11个f(s)，依次再求i=4，3，2，1 的各11个f(s)，其中，s表示剩余承重量，s=1, ..., s=10 这几列对应的数值表示的是 f(s)，即最大价值。
最终选择将5个x1，即5个a，放入包中
将问题拓展到matlab程序中，用程序计算：
输出结果：
上期的0-1背包问题
已知6种物品，假设每种物品个数只有一个，一个可载重量为W=60千克的背包，物品i=1,2,3,4,5,6的重量为15,17,20,12,9,14，价值为32,37,46,26,21,30，在装包时每一件物品可以装入，也可以不装，如何确定装包，使所装包的总价值最大？
鉴于matlab中自带求解此类问题的函数：
bintprog函数
程序调用如下：f中的-1时将max问题，转化为min问题，A为重量矩阵，f为价值矩阵，b为包的承重量
结果如下：可以看出，选择装第2，3，5，6件物品，价值最大为134，与贪心算法130相比，得到最优解。
好了，以上便是本期推送的全部内容，这里是Building可视库，我们下期见吧~
参考说明：
代码来源CSDN：心态与做事习惯决定人生高度
《优化与决策》.王玉英
扩展阅读：
图文+模拟 | 阿明