0-1背包问题

0-1背包问题是动态规划的经典组合优化问题。

问题描述

给定一组物品，每个物品有重量 w[i] 和价值 v[i]，在背包容量为 W 的限制下，选择物品使得总价值最大。每个物品只能选择一次（0或1）。

需要一个二维数组的动态规划来解决，因为仅考虑重量或仅考虑物品都无法完整描述状态。

分为两种情况：

如果不包含第 j 个物品，则最大价值等于同样 x 承重、前 j-1 个物品时的最大价值。

如果包含第 j 个物品，则价值为减去该物品重量后的背包承重、前 j-1 个物品时的最大价值加上该物品价值。

对于含 n 个物品的最优解，前 n-1 个物品一定是去掉第 n 个物品重量后的承重下的最优解。

时间复杂度 O(nW)，其中 n 为物品数，W 为背包容量。