背包问题九讲02-完全背包问题总结

1.题目描述：

假设有n件物品，每件物品都有value，和cost属性，现有一个容量为v的背包，现在每件物品都有无限件可以选择，请问为了使背包的总价值最大，我们该怎么挑选放入背包的物品，输出我们的最大总价值

2.思路：

不同于01背包问题的完全背包问题，和01背包问题有所不同，完全背包问题强调了，每种物品都有无限件可以选取，那么我们最终要检查的状态就不在是01背包问题中的O(V*N)而是扩展成O(V*SUM( V/cost[i]))件物品，显然因为扩展了可能选择的情况，我们的时间复杂度激素飙升，在背包容量非常大，并且物品的耗费很小的时候，这种算法的时间复杂度有些显得力不从心

但是我们还是来写一下还方法的状态和状态专业方程，位我们接下来的优化提供契机

定义状态：

dp[i][j]:在背包容量为j的情况下，我们在放入前i件物品的时候（最大选择上线是V/cost[i]）可以获得的最大价值

状态转移方程：

dp[i][j]=max(dp[i][j-k*cost[i]]+k*value[i])  //K从0~V/cost[i](选择下界)

3.简单优化：

1.思路上的优化：

我们不好理解哇暖背包问题的话，其实不妨把完全背包问题转化成01背包问题，我们这样来看待我们的完全背包，既然每一个物品都有V/cost[i]中选择方式，那么我们就不妨从01背包的思路入手，我们将物品机体扩充，每件物品都有V/cost[i]件，那么我们就将问题装化成了有n*sum(V/cost[i])件物品的01背包问题了，但是这种想法上的优化对于我们优化时间复杂度没有任何实际上的作用，我们需要扫描的状态的数目仍然是O(V* n*sum(V/cost[i]))中状态，但是，这种事路其实给我们提供了一种01背包和完全背包之间的联系

2.01背包思路的进一步优化：

我们可以发现，每一件物品既然都要拆成n*sum(V/cost[i])件物品，我们是选择每件物品单独来作为一种情况来进行组装，但是我们仔细想想就会发现，实际上，我们为了找过所有的情况，没有必要拆除那么多的物品，想一下二进制的原理，任何一个数我们都可以由二进制数目进行组合来得到，那我们同样的，如果我们将每个物品最多拆成二进制个话，我们完全就可以实现我们需要的所有的状态了

比如，为了实现表示我们二进制的100（4），我们没必要拆出4个状态：1,10,11,100，我们只需要2^k=4,k=2种状态就可以了，也就是说，我们最多只需要1和10就能够高速的实现我们的所有的状态的组合

这样的话，我们来回到正题上，对于完全背包的话，我们每个物品只需要cost[i]*2^k<=V,也就是说log(V/cost[i])个状态就好了

那么我们01背包需要的扫描的状态数目就是

O(V*n*log(V/cost[i]))

我们现在来比较一下两个状态：

O(V*n*log(V/cost[i]))
O(V*n*V/cost[i])

显而易见，我们在01背包的思路之上，成功的优化了我们的时间复杂度

PS：这里我们选择了2^k来拆，其实根据个人喜好3^k,4^k都是可以的，但是在计算时间复杂度的时候我们统一是用2^k来作为标准的

3.O(V*N)优化思路：

其实我们的O(V*N)的思路其实很好得到，但是这里面我们的额优化思路和我们的01背包的思路是不一样的，我们还是从前往后扫，一会我来解释一下这一点的额含义是什么

先上核心代码：

for(int i=1;i<=n;i++)
{
	for(int j=0;j<=v;j++)  //可以黑箱优化 
	{
		dp[i][j]=max(dp[i][j],dp[i][j-cost[i]]+value[i]);
	}
}

PS:所谓的常数优化，就是我们每次起点都是cost[I]，在我们的物品的cost比较高的时候，该优化的效果是很可观的

我们这样优化的思路其实很简单

首先，我们这样优化是建立在内层循环是从前往后进行的，每一次，我们之前的状态都是已经计算过的

那么我们再来考虑我们原先的没有优化的时候的状态

dp[i][j]=max(dp[i][j-k*cost[i]]+k*value[i])  //K从0~V/cost[i](选择下界)

在这里我们发现，我们的k次优化是不断递增的，也就是说我们下一次的k可以通过k-1已经计算出来的值（这个计算出来的值已经是前一段的k是最优的），我们直接拿这个最优解和我们的当前的解进行比较就可以了

4.空间复杂度的优化：

我们其实没必要开辟那么多的，我们只需要之前计算的数值和当前位置的数据（当前的数据是一个都不取）

黑箱优化：

void absolutepackage(int cost,int value)
{
	for(int i=cost;i<=v;i++) dp[i]=max(dp[i],dp[i-cost]+value);
}

void test()
{
	for(int i=1;i<=n;i++) absolutepackage(cost[i],value[i]);
}

秒客网