[Algorithm]Knapsack Problem

给定体积为V的背包，和n件物品，物品i的体积和价值分别用c[i]和w[i]来表示，给定不同的规则，我们要求背包能容纳的最大价值。这是背包问题的一般背景，根据具体的规则有不同的分类。普遍来讲背包问题是NP-complete问题，没有严格的多项式时间的解，只有伪多项式时间的解。本文不会太过深入，只会涉及01背包问题和完全/无界背包问题，如果想要了解更多的背包问题可以参考背包九讲。

01背包问题

最基本的背包问题，每个物品要不放一次要不不放。我们用dp[i][v]来表示用前i件物品放体积为v的背包所能达到的最大价值，那么我们有递推公式：

• dp[i][v] = max(dp[i - 1][v], dp[i - 1][v - c[i]] + w[i])

前一项代表不放当前物品，后一项代表放。那么根据这个递推公式我们很容易就能得到时间O(Vn)和空间O(Vn)的解。时间的部分我们没有办法继续优化，那么从空间下手，用一维数组的难点就在于我们要取dp[i - 1][v - c[i]]的值而这个值在我们遍历到dp[i][v]的时候已经被覆盖了。但是我们仔细想想，dp[i - 1][v - c[i]]被覆盖的原因是由于我们从左向右遍历，那么为何不反过来从右向左呢？只要改变遍历方向，我们就可以把空间复杂度从O(Vn)降低到O(V)。代码如下：

	int knapsack(int V, vector<int>& v, vector<int>& w)
	{
	if(V <= 0 || v.empty() || w.empty())return 0;
	vector<int> dp(V + 1, 0);
	for(int i = 1; i <= V; ++i)
	{
	for(int j = v.size() - 1; j >= v[i]; --j)dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
	}
	return dp[v.size() - 1];
	}

view raw 01_knapsack.cxx hosted with ❤ by GitHub

完全/无界背包问题

如果每个物品有无限多个，我们应该怎么做？这个时候递推公式应该变为：

• dp[i][v] = max(dp[i - 1][v - k * c[i]] + k * w[i])  0 <= k * c[i] <= v                                           

根据这个公式每个状态求解的时间复杂度为O(v / c[i])，整体看来还是比较慢的。我们需要更快的时间复杂度就需要更好的递推公式，我们考虑这个递推公式：

• dp[i][v] = max(dp[i - 1][v], dp[i][v - c[i]] + w[i])

只有第二项和01背包不同，直观地理解，相对于考虑只放一次，我们应该考虑已经放了物品i的情况，这也就是为什么是dp[i][v - c[i]] + w[i]而不是dp[i - 1][v - c[i]] + w[i]。从数学角度来说，如果我们递归地展开max中的第二项，可以得到和第一个递推公式相同的结果：

• dp[i][v] = max(dp[i - i][v], dp[i - 1][v - c[i]] + w[i], dp[i - 1][v - 2 * c[i]] + 2 * w[i] ...)

那么根据这个公式我们可以得到时间O(Vn)和空间O(V)的结果。有趣的是，和之前的实现方式相反，我们完全可以顺序遍历，因为我们需要用dp[i][v - c[i]] + w[i]而不是dp[i - 1][v - c[i]] + w[i]，代码如下：

	int knapsack(int V, vector<int>& v, vector<int>& w)
	{
	if(V <= 0 || v.empty() || w.empty())return 0;
	vector<int> dp(V + 1, 0);
	for(int i = 1; i <= V; ++i)
	{
	for(int j = v[i]; j < v.size(); ++j)dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
	}
	return dp[v.size() - 1];
	}

view raw unbounded_knapsack.cxx hosted with ❤ by GitHub

伪多项式时间

我们经常用O(f(N))来表示时间复杂度，那么N到底表示什么，对于一般的数据结构和算法N是数据的规模，比如排序算法O(n * logn)中的n是数组的长度。但是考虑素数的试除法，对于大小为n的整数，时间复杂度为O(sqrt(n))，但是这里的n是数字的大小。这里两个n代表了两个完全不同的东西，我们需要统一表示输入数据的大小。

背包问题有O(Vn)时间的解法，却还是NP-complete问题，这是为什么呢？因为O(Vn)是伪多项式时间，什么是伪多项式时间，根据维基百科的解释如下：

    In computational complexity theory, a numeric algorithm runs in pseudo-polynomial time if its running time is polynomial in the numeric value of the input, but is exponential in the length of the input – the number of bits required to represent it.

在这里我们得到了一个概念，用输入bit长度来表示输入的大小。对于排序算法假设每个数是64/128位，那么输入就是64n/128n，这样时间复杂度还是可以表示成输入的多项式，这对于其他的数据结构也是类似的。对于试除法来说，输入是一个整数n，我们不可能对其位数做出限制，因为那样我们对时间复杂度的分析就没有意义了。输入位数的大小是logn，时间复杂度是O(n^(1/2)) = O((2 ^ logn) ^ (1/2))，和输入位数成指数级的关系，所以根据定义是伪多项式时间。同样对于背包问题来说，我们在这不做严格的数学证明，输入V的位数是logV，但是在时间复杂度表达式中变成了V，也是呈指数的关系，所以是伪多项式时间。