动态规划-0-1背包.ppt

数据结构实训 适用专业： 软件工程（本科） 学时： 32 实训3：动态规划-0-1背包问题 问题描述：给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大? 对于一种物品，要么装入背包，要么不装。所以对于一种物品的装入状态可以取0和1.我们设物品i的装入状态为xi,xi∈(0,1)，此问题称为0-11背包问题 0-1背包问题 0-1背包问题是一个特殊的整数规划问题。可描述如下： 过程分析 背包的最大容量为10，那么在设置数组m大小时，可以设行列值为5和10，那么，对于m(i,j)就表示可选物品为i…n背包容量为j(总重量)时背包中所放物品的最大价值。 最优值过程分析 背包中的物品设为空，首先，我们先对物品n放入背包的情况做分析,即在总重量分别为0到10时,如何放置物品n,使总价值最大，此时要确定m(5,0..10)11个元素的值。 最优值过程分析 然后，我们在对物品5处理后的基础上，对物品4进行分析。此时我们的任务是要确定m(4,0..10)11个元素的值。用同样的方法，对物品4的处理有两种情况：w4大于j和w4小于j。 最优值过程分析 最优值过程分析 以此类推，完成m(4,6..10)的最优值 最优值过程分析 填充m(3,1..10)的最优值 最优值过程分析 填充m(2,0..10)的最优值 最优值过程分析 计算原问题的最优值 最优值过程分析 m的最终结果如下表 递归定义最优值 由前面的最优值过程分析实例，根据0-1背包问题的最优子结构性质，可以建立计算m(i，j)的递归式： 构造最优解 我们可根据c列的数据来构造最优解，从i=1,j=c即m(i,j)开始，如果m(i,j)==m(i+1,j),则物品wi没有装入背包，从而xi=0，否则，物品wi装入背包，相应的xi=1，此时，为了确定其后继即k=i+1的xk的值，我们应在k行寻找新的j值作为参照。 构造最优解 结果示例： 动态规划思想 动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题。 但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。 如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，为此，可以用一个表来记录所有已解决的子问题的答案而不管该答案是否用到，这就是动态规划的基本思想。 动态规划基本步骤 找出最优解的性质，并刻划其结构特征。 递归地定义最优值。 以自底向上的方式计算出最优值。 根据计算最优值时得到的信息，构造最优解。 1-最优子结构性质 最优子结构性质：动态规划算法的第一步是要刻画最优解的结构，即当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法求解的显著特征 2-递归定义最优值 由前面的最优值过程分析实例，根据0-1背包问题的最优子结构性质，可以建立计算m(i，j)的递归式： 3-计算最优值 根据前边的分析过程设计相应的算法，我们可从wn开始以自底向上的方式计算出最优值；完成m(1..n,0..c)的数据填充 4-构造最优解 我们可根据c列的数据来构造最优解，从i=1,j=c即m(i,j)开始，如果m(i,j)==m(i+1,j),则物品wi没有装入背包，从而xi=0，否则，物品wi装入背包，相应的xi=1，此时，为了确定其后继即k=i+1的xk的值，我们应在k行寻找新的j值作为参照。对物品n，直接由m(n,j)是否为0确定xn的值是0或1 实训2：设计要求 窗体设计基本要求：用户输入信息：物品个数、物品重量及价值、背包容量；输出信息：装入背包的物品序号、背包的总重量以及所装入物品的总价值。在此基础上扩展功能需求。 矩阵连乘 问题：设有给定n个矩阵{A1,A2,...,An}，其中Ai与Ai+1是可乘的，i=1,2,...,n-1。考察这n个矩阵的连乘积A1A2...An。 假设给定两个矩阵A1,A2, 它们的维数分别是m*n,n*p,则计算A1A2的标准算法怎样设计？ 矩阵连乘 多矩阵连乘满足结合律，假设给定三个矩阵A1,A2, A3的维数分别是10*100，100*5，5*50， 问： A1,A2, A3有多少种组合方式，不同组合方式下各进行多少次数乘运算？ 矩阵连乘 矩阵连乘问题即是对于给定n个矩阵｛A1,A2,…,An｝，其中Ai与Ai+1是可乘的，i=1，2…，n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。 如何确定一个矩阵连乘积的最优的计算次序，是我们要解决的根本问题，通过传统的什么方法可以找出最优解？ 矩阵连乘 设有