0-1 背包问题

定义

0-1 背包问题:给定 n 件物品,各有重量和价值,以及容量为 W 的背包,每件物品要么整件放入要么不放,求能装入的最大总价值。它是经典的 NP 难组合优化问题。

算法

常用动态规划:dp[j] 表示容量 j 下的最大价值,逐件物品按容量从大到小更新 dp[j] = max(dp[j], dp[j-w]+v),时间复杂度 O(nW)。该复杂度与数值 W 相关,属伪多项式时间。其他方法包括回溯加剪枝、分支限界,以及近似方案 FPTAS。

变体

完全背包(每件可选无限次,内层循环改为正序)、多重背包(件数有限,可二进制拆分优化)、分组背包与二维费用背包等,构成一族经典模型。

应用

资源分配、投资组合选择、货物装载、云计算任务放置等场景都可抽象为背包模型。