好记性不如铅笔头

java, 数据结构与算法, 编程, 编程之美

算法学习笔记:动态规划

最近在学习《 编程之美 》这本书,书中提到了很多很经典的算法问题和实现,学起来真是耗费脑细胞啊,书中在多个问题中涉及到了【 动态规划 】算法,由于作者不是计算机专业出身,没有学习过这个算法,这里就把这个算法自己学习备份一下。如果有错误,请各位大牛指正,不胜感激。

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的基础上,减少了空间复杂度。

发表评论

3 × 3 =

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据