滚动数组如何实现01背包问题的长尾词疑问？

本文共计1717个文字，预计阅读时间需要7分钟。

01背包问题定义：在\(M\)空间内，将\(N\)件物品取出放入\(V\)空间为背包，每件物品的体积为\(V_1, V_2, \ldots, V_n\)，与相应的价值为\(W_1, W_2, \ldots, W_n\)。01背包的约束条件是给定的\(V\)空间容量。

01背包

定义：在\(M\)件物品取出若干件放在空间为\(V\)的背包里，每件物品的体积为\(V_1\)，\(V_2\)至\(V_n\)，与之相对应的价值为\(W_1\)，\(W_2\)至\(W_n\)。

01背包的约束条件是给定几种物品，每种物品有且只有一个，并且有权值和体积两个属性。

在01背包问题中，因为每种物品只有一个，对于每个物品只需要考虑选与不选两种情况。

（故称为01背包。）

解决这个问题我们需要从前一个状态递推到下一个状态，最终递推到我们想要的状态。

01背包题目的雏形是：

有\(N\)件物品和一个容量为\(V\)的背包。第\(i\)件物品的体积是\(c[i]\)，价值是\(w[i]\)。求解将哪些物品装入背包可使价值总和最大。

这个问题核心的矛盾有两处：1.背包的容量，2.所装物品的价值。

所以，我们不妨假设背包内物品的价值为$ F(I,C)$ 。