动态规划算法：0-1背包问题.ppt

动态规划算法原理将待求解的问题分解成若干个相互联系的子问题 先求解子问题 然后从这些子问题的解得到原问题的解 对于重复出现的子问题 只在第一次遇到的时候对它进行求解 并把答案保存起来 为了不去求解相同的子问题 引入一个数组 把所有子问题的解存于该数组中 这就是动态规划所采用的基本方法 动态规划采用由下至上 Bottom Up 计算策略 例 输出Fibonacii数列的第n项的递归算法 includeintfib intn if n 1 return1 elsereturnfib n 1 fib n 2 voidmain intn scanf d 在上面的递归算法中存在多次计算同一个子问题 如 fib 2 如果能将这样的子问题的解用数组保存起来 即可以加快求解的过程 即采用动态规划方法 输出Fibonacii数列的第n项的动态规划算法 include defineMAX50intfib intn inti a MAX a 1 a 2 1 for i 3 i n i a i a i 1 a i 2 returna n voidmain intn scanf d 例1 0 1背包问题有一个负重能力为m的背包和不同价值v i 不同重量w i 的物品n件 在不超过负重能力的前提下 从这n件物品中任意选择物品 使这些物品的价值之和最大 算法思想1 设m i j 用来表示从第i项物品开始到第n项物品中区取出装入体积为j的背包的物品的最大价值 其中i的范围为1到n 其中j的范围为0到c 程序要寻求的解为m 1 c 可以发现 m n j 在当j 0并且j w n 时等于0 否则等于v n 当前的背包容量j大于等于物品重量w i 时 m i j 是下面两个量的最大值 m i 1 j 和m i 1 j w i v i 当前的背包容量j小于物品重量w i 时 m i j 等于m i 1 j m n j v n 当j w n 0当j 0并且j w n 程序1 动态规划法 include defineMAX20intn c w MAX v MAX m MAX MAX 0 voiddisp inti for i 1 i n i if m i c m i 1 c printf 5d 5d n w i v i voidknapsack inti j for j w n j 1 i for j w i jm i 1 j w i v i m i j m i 1 j elsem i j m i 1 j w i v i voidmain inti j printf 输入物品种数 scanf d 算法思想2 设m i j 用来表示从前i项物品中区取出装入体积为j的背包的物品的最大价值 其中i的范围为1到n 其中j的范围为0到c 程序要寻求的解为m n c 可以清楚地发现 m 0 j 对所有的j的值为0 m i 0 对所有的i的值为0 当前的体积j大于等于w i 时 m i j 是下面两个量的最大值 m i 1 j 和m i 1 j w i v i 当前的体积j小于w i 时 m i j 等于m i 1 j 程序2 动态规划法 include defineMAX20intn c w MAX v MAX m MAX MAX 0 voidknapsack inti j for i 1 i w i 1 显示所取的物品及其重量 其中一个解 对数组m的最后一列检查来求解voiddisp inti j i n while m i c m i 1 c i