如何使用滚动数组实现01背包问题？

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

01背包定义：在(M)物品中，将干燥条件放置在(V)空间的背包里，每件物品的体积为(V_1)，(V_2)至(V_n)，与其对应的重量为(W_1)，(W_2)至(W_n)。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)$ 。