动态规划背包问题算法分析,动态规划法求解背包问题

　　00-1010动态规划算法动态规划算法的思想最优性原则动态规划算法的三个特点动态规划算法中的0/1背包问题动态规划算法的优点总结

目录

　　00-1010动态规划算法处理多阶段复杂决策问题。动态规划算法类似于分治算法。它的基本思想是把要解决的问题分解成若干个子问题(阶段)，然后分别求解每个子问题(阶段)，最后将子问题的解组合起来得到原问题的解。但与分治算法不同的是，子问题往往不是独立的，而是相互关联又互不相同的。

　　动态规划算法问题求解的目标是获得导致问题最优解的最优决策序列(最优策略)。对于一个决策序列，可以用一个数值函数(目标函数)来衡量这个决策的质量。

　　00-1010动态规划算法最优性原理：一个最优决策序列具有这样一个性质，即不管初始状态和第一个决策如何，对于前一个决策形成的状态，其余的决策必须根据前一个决策产生的新状态形成一个最优决策序列。

　　最优性原理体现在问题的最优子结构特征中。对于一个问题，如果一个大规模相似子问题的最优解可以由一个小规模子问题的最优解得到，则最终可以得到给定问题的最优解，即该问题最优解所包含的子问题的最优解。这个性质叫做最优子结构性质。由较小问题的解构造较大问题的解时，最优子结构的特点是只需要考虑子问题的最优解，然后由子问题的最优解自底向上递归构造整个问题的最优解。保证了通过求解子问题的最优解可以得到原问题的最优解，最优子结构的特征是动态规划算法求解问题的必要条件。

　　00-1010如果所解决的问题满足最优性原理，则意味着用动态规划算法解决问题是可能的。在分析问题的最优子结构时，所用的方法是通用的。需要注意的是，描述问题最优子结构的方法有很多种，有些表示方法求解速度更快(占用空间少，问题维数低)。定义递归最优解。动态规划的每一个决策都依赖于子问题的解。动态规划算法求解优化问题的步骤是3360找出最优解的结构。具体要看问题是否满足最优子结构特征。其次，递归定义一个最优解的值，即在原问题和子问题之间构造一个递归方程。原问题的最优解可以通过子问题的最优解得到。自下而上计算最优解的值(最优解的目标函数值)。子问题的分解是基于原问题的分解，这些子问题的分解过程是相互独立的。在分解原问题的过程中，会出现大量共享的重叠子问题。为了避免大量重叠子问题的重复计算，一般动态规划算法都是自下而上，每个问题只求解一次，保存求解子问题的最优值。当需要求解这个子问题时，可以在一个常数时间内检查结果，而不是递归求解每个问题，从而提高动态规划算法的效率。

　　00-1010 0/1背包问题的规则是物品不允许拆分，即只有当物品处于放入和不放入两种基本状态时，利用动态规划算法找出如何放置物品，背包中物品的总价值才能达到最高。

　　例子

　　有一个负重10的背包。文章有四种。重量

　　包裹算法设计与分析；导入Java。util。数组；导入Java。util。扫描仪；//m表示的是背包的容量，一个表示有多少种类的物品，数组英语字母中的第二十三个字母用与存放每类物品的重量，数组英国压力单位用于存放每类物品的价值public class my { public static void main(String[]args){ Scanner Scanner=new Scanner(system。在)；System.out.print(请输入背包的容量：);int m=扫描仪。nextint()；扫描仪inScanner=新扫描仪(系统。在)；System.out.print(请输入物品的个数：);int a=在扫描仪中。nextint()；int[]w=new int[a 1]；System.out.print(请输入物品的重量： );for(int I=1；I=a；I){ w[I]=在扫描仪中。nextint()；} int[]val=new int[a 1]；System.out.print(请输入物品的价值： );for (int i

　　= 1; i <= a; i++) { val[i] = inScanner.nextInt(); } int n = val.length; int[][] path = new int[n +1][m+1 ]; //创建二维数组 //v[i][j]：表示在前i个物品中能够装入容量为j的背包中的最大价值 int[][] v = new int[n +1][m + 1]; //初始化第一行和第一列 for (int i = 0; i < v.length; i++) {//v.length:获取二维数组的行数 v[i][0] = 0;//将第一列设置为0 } for (int i = 0; i < v[0].length; i++) {//v[0].length：获取二维数组的列数 v[0][i] = 0;//将第一行设置为0 } for (int i = 1; i < v.length; i++) {//int i = 1 不处理第一行 for (int j = 1; j < v[0].length; j++) {//int j = 1 不处理第一列 if (w[i - 1] > j) { v[i][j] = v[i - 1][j]; } else { if (v[i - 1][j] < (val[i - 1] + v[i - 1][j - w[i - 1]])) { v[i][j] = val[i - 1] + v[i - 1][j - w[i - 1]]; //把当前情况记录到path path[i][j] = 1; } else { v[i][j] = v[i - 1][j]; } } } } //输出二维数组： for (int[] ints : v) { System.out.println(Arrays.toString(ints)); } //输出最后我们是放入的那些商品 int i = path.length - 1;//行的最大下标 int j = path[0].length - 1;//列的最大下标 while (i > 0 && j > 0) {//从path的最后开始找 if (path[i][j] == 1) { System.out.printf("第%d个商品放入背包n", i-1); j -= w[i - 1]; } i--; } } }输入一个背包容量为10，里面有4类物品，物品的重量分别为2，3，4，7，物品的价值分别为1，3，5，9

　　结果

动态规划算法的优点

若要解一个给定问题，我们需要解其不同部分（即子问题），再合并子问题的解以得出原问题的解。 通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量： 一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。 这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。

小结

以上就是针对动态规划算法的详细分析，利用动态规划算法可以避免重复计算多次子问题，提高效率，使计算机的性能更好！

　　到此这篇关于Java使用动态规划算法思想解决背包问题的文章就介绍到这了,更多相关Java背包问题内容请搜索盛行IT以前的文章或继续浏览下面的相关文章希望大家以后多多支持盛行IT！

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。