完全背包问题的改进实现

完全背包问题就是每个东西都不限数量的，01背包问题呢，则是限制数量为1

对于改进了的01背包问题，也有改进了的背包问题，他们的想法上是一致的，只不过实现上有了一点差别

也是比较简单的，亲手debug一下吧

/**
 * 完全背包问题<br/>
 * 
 * f[v]=max{f[w],f[w-w[i]]+v[i]}<br/>
 * 也就是f[i][v] = max{f[w],f[w-w[i]]+v[i]}<br/>
 * 时间复杂度O(WN)<br/>
 * 空间复杂度O(W)<br/>
 * 
 * @author Joeson
 * 
 */
public class CompletePack
{

	public static void main(String[] args)
	{
		int[] value = new int[] { 12, 10, 20, 35, 20 };
		int[] weight = new int[] { 2, 1, 3, 2, 2 };
		int W = 5;
		System.out.println(knapsack(value, weight, W));
	}

	public static int knapsack(int[] v, int[] w, int W)
	{
		int[] tmp = new int[W + 1];

		for (int i = 0; i < v.length; i++)
			completePack(tmp, v[i], w[i], W);

		return tmp[W];
	}

	/**
	 * 
	 * @param tmp
	 *            辅助数组
	 * @param value
	 *            当前v[i]的价值
	 * @param weight
	 *            当前w[i]的重量
	 * @param W
	 *            总重量
	 */
	public static void completePack(int[] tmp, int value, int weight, int W)
	{
		for (int i = 0; i <= W; i++)
		{
			tmp[i] = i - weight >= 0 ? Math
					.max(tmp[i], tmp[i - weight] + value) : tmp[i];
		}
	}
}

完全背包问题的改进实现,布布扣,bubuko.com

完全背包问题的改进实现

原文：http://blog.csdn.net/chenxuegui1234/article/details/20791743