最近在学习《 编程之美 》这本书,书中提到了很多很经典的算法问题和实现,学起来真是耗费脑细胞啊,书中在多个问题中涉及到了【 动态规划 】算法,由于作者不是计算机专业出身,没有学习过这个算法,这里就把这个算法自己学习备份一下。如果有错误,请各位大牛指正,不胜感激。
CONTENTS
参考文章:
【 http://www.cnblogs.com/sdjl/articles/1274312.html 】
【 http://hawstein.com/posts/dp-knapsack.html 】
题目:
话说有一哥们去森林里玩发现了一堆宝石,他数了数,一共有n个。 但他身上能装宝石的就只有一个背包,背包的容量为C。这哥们把n个宝石排成一排并编上号: 0,1,2,…,n-1。第i个宝石对应的体积和价值分别为V[i]和W[i] 。排好后这哥们开始思考: 背包总共也就只能装下体积为C的东西,那我要装下哪些宝石才能让我获得最大的利益呢?
实现:
题目和大致的解题思路上述两篇文章已经写得非常不错了,作者这里简单的备份下java的实现代码:
备忘录实现:
private static int diamondTest1(int[][] diamonds, int currCapacity) { /* maxValue[i][j]:表示当钻石总数为i个,当前剩余容积为j的时候,总数的最大价值。 */ int [][]maxValue = new int [diamonds.length + 1][currCapacity + 1]; for (int[] is : maxValue) { Arrays.fill(is, -1); } internelDiamondTest1(maxValue, diamonds, diamonds.length, currCapacity); return maxValue[diamonds.length][currCapacity]; } private static int internelDiamondTest1(int[][] maxValue, int[][] diamonds,int currDiaNum, int currCapacity) { if (maxValue[currDiaNum][currCapacity] != -1) { return maxValue[currDiaNum][currCapacity]; } if (currDiaNum == 0) { maxValue[currDiaNum][currCapacity] = 0; return maxValue[currDiaNum][currCapacity]; } if (currDiaNum == 1) { maxValue[currDiaNum][currCapacity] = currCapacity >= diamonds[currDiaNum -1][0] ? diamonds[currDiaNum -1][1]:0; return maxValue[currDiaNum][currCapacity]; } if (currCapacity >= diamonds[currDiaNum-1][0]) { maxValue[currDiaNum][currCapacity] = max( internelDiamondTest1(maxValue, diamonds, currDiaNum-1, currCapacity-diamonds[currDiaNum-1][0]) + diamonds[currDiaNum-1][1], internelDiamondTest1(maxValue, diamonds, currDiaNum-1, currCapacity) ); }else { maxValue[currDiaNum][currCapacity] = internelDiamondTest1(maxValue, diamonds, currDiaNum-2, currCapacity); } return maxValue[currDiaNum][currCapacity]; }
思路很简单,就是通过函数递归的方式,一层一层的求解问题,以可用钻石数目的不断递减来求解。
两层循环求解:
private static int diamondTest2(int[][] diamonds, int currCapacity) { /* maxValue[i][j]:表示当钻石总数为i个,当前剩余容积为j的时候,总数的最大价值。 */ int [][]maxValue = new int[diamonds.length + 1][currCapacity + 1]; /* 当钻石的总数为0时,不管当前剩余容积多大,总价值都为0 */ for (int i = 0; i <= currCapacity; i++) { maxValue[0][i] = 0; } for (int i = 1; i <= diamonds.length; i++) { /* 由于i值是递增的, 因此每次内层i循环后,diamonds[i-1][...]的值已经是定值了 */ for (int j = 0; j <= currCapacity; j++) { /* 当讨论前i个宝石装入背包的时候, 其实是在考查第i-1个宝石装不装入背包(因为宝石是从0开始编号的)。第i个宝石在数组中的位置是diamond[i-1][] */ if (j > diamonds[i-1][0]) { maxValue[i][j] =max(maxValue[i-1][j - diamonds[i-1][0]] + diamonds[i-1][1], maxValue[i - 1][j]) ; }else { maxValue[i][j] = maxValue[i-1][j]; } } } return maxValue[diamonds.length][currCapacity]; }
以可用钻石数目的不断递增来求解,通过可用钻石数目的累加达到最后的最大值。
两层循环求解A:
/* diamondTest2A 函数是diamondTest2的第二种版本 */ private static int diamondTest2A(int[][] diamonds, int currCapacity) { int [][]maxValue = new int[diamonds.length + 1][currCapacity + 1]; for (int i = 0; i <= diamonds.length; i++) { for (int j = 0; j <= currCapacity; j++) { maxValue[i][j] = i == 0 ? 0:maxValue[i-1][j]; if (i > 0 && j > diamonds[i-1][0]) { maxValue[i][j] =max(maxValue[i-1][j-diamonds[i-1][0]] + diamonds[i-1][1], maxValue[i - 1][j]) ; } } } return maxValue[diamonds.length][currCapacity]; }
在两层循环求解的基础上稍微修改的一下。
两层循环求解B:
/* diamondTest2B 函数是diamondTest2的第三种版本 */ private static int diamondTest2B(int[][] diamonds, int currCapacity) { int [][]maxValue = new int[diamonds.length + 1][currCapacity + 1]; for (int i = 0; i <= diamonds.length; i++) { /* 在本循环内,diamonds[i-1][...]的值已经是计算过的定值了, * 而maxValue[i][j]的计算全部是由maxValue[...][j-..]计算的,与maxValue[...][j]无关, * 所以j可以用递减序来计算 */ for (int j = currCapacity; j >= 0; j--) { maxValue[i][j] = i == 0 ? 0:maxValue[i-1][j]; if (i > 0 && j > diamonds[i-1][0]) { maxValue[i][j] =max(maxValue[i-1][j-diamonds[i-1][0]] + diamonds[i-1][1], maxValue[i - 1][j]) ; } } } return maxValue[diamonds.length][currCapacity]; }
通过分析代码可知,内部的第二层for循环可以采用递减的方式求解。
两层循环求解C:
/* diamondTest2C 函数是diamondTest2的第四种版本 */ private static int diamondTest2C(int[][] diamonds, int currCapacity) { int []maxValue = new int[currCapacity + 1]; for (int i = 0; i <= diamonds.length; i++) { /* 在逆序的基础上,可以通过减少本循环内的maxValue的维度来达到最小的空间复杂度 */ for (int j = currCapacity; j >= 0; j--) { if (i > 0 && j > diamonds[i-1][0]) { maxValue[j] =max(maxValue[j-diamonds[i-1][0]] + diamonds[i-1][1], maxValue[j]) ; } } } return maxValue[currCapacity]; }
在两层循环求解B的基础上,减少了空间复杂度。
发表评论