knapsack01

解决经典的0-1背包问题,在限定的总重量内选择物品使得总价值最大,每个物品只能选择一次。

输入配置

物品列表 (JSON格式)

背包容量

物品1

重量: 2

价值: 3

物品2

重量: 3

价值: 4

物品3

重量: 4

价值: 5

物品4

重量: 5

价值: 6

执行过程

步骤 1 / 24

初始化DP表，dp[i][w]表示前i个物品在容量w时的最大价值

物品\容量	0	1	2	3	4	5	6	7	8
0	0	0	0	0	0	0	0	0	0
1	0	0	0	0	0	0	0	0	0
2	0	0	0	0	0	0	0	0	0
3	0	0	0	0	0	0	0	0	0
4	0	0	0	0	0	0	0	0	0

速度:慢速正常快速超快

当前单元格

来源单元格

最终结果

算法说明

0-1背包问题：在限定容量内选择物品使总价值最大，每个物品只能选0或1次。使用动态规划求解，时间复杂度O(n×W)。

函数签名

function knapsack01(
  items: KnapsackItem[],
  capacity: number,
  includeDpTable?: boolean
): KnapsackResult

interface KnapsackItem {
  name?: string
  weight: number
  value: number
}

interface KnapsackResult {
  maxValue: number
  selectedItems: number[]
  dpTable?: number[][]
}

参数

参数名	类型	必填	说明
items	KnapsackItem[]	是	物品数组,每个物品包含重量和价值
capacity	number	是	背包容量
includeDpTable	boolean	否	是否在结果中包含DP表(用于调试),默认false

KnapsackItem 结构:

属性	类型	必填	说明
name	string	否	物品名称(用于显示)
weight	number	是	物品重量
value	number	是	物品价值

返回值

类型	说明
KnapsackResult	背包问题结果对象

KnapsackResult 结构:

属性	类型	说明
maxValue	number	在限定容量内可获得的最大价值
selectedItems	number[]	选中的物品索引数组
dpTable	number[][]	DP表(可选,仅当includeDpTable为true时)

工作原理

1. 创建DP表: 创建一个 (n+1) × (capacity+1) 的二维数组,其中 n 是物品数量
2. 填充DP表: 对每个物品和每个容量,决定是否选择该物品
   • 不选择: dp[i][w] = dp[i-1][w]
   • 选择: dp[i][w] = dp[i-1][w-weight] + value
   • 取两者最大值
3. 回溯找出选中物品: 从 dp[n][capacity] 开始回溯,判断每个物品是否被选中
4. 返回结果: 返回最大价值和选中的物品索引

时间复杂度: O(n×W),其中 n 是物品数量,W 是背包容量
空间复杂度: O(n×W)