0-1背包问题（Knapsack）.md

0-1背包问题（Knapsack）

问题描述

有一个容量为C（Capacity）的背包。 现在有N件物品，编号为1...n，每件物品的重量为w[i]，价值为v[i]。 在不超过C前提下，如何选择放入背包中的物品，使得总价值最大。

状态定义

dp[i][c]: 将前i个物品放入容量为c的背包中，得到的最大价值

状态转移

对于第i个物品，可以选择拿或者不拿：

dp[i][c] = max{dp[i-1][c], dp[i-1][c-w[i]] + v[i]}

• dp[i-1][c]：不拿第i件物品，那么问题变为在前i-1个物品中的最大价值.
• dp[i-1][c-w[i]] + v[i]：拿第i件物品，加上其价值v[i]，容量放得下dp[i-1][c-w[i]].

优化空间，使用一维数组

dp = [0] * (C + 1)
for i = 0..N-1 //左闭右闭
    for c = C..w[i]
        dp[c] = max{dp[c], dp[c-w[i]] + v[i]}

• dp长度为C+1：下标最大值为C，语义与下标值相同，可以直接与w[i]比较
• 内循环倒序：第i次的dp依赖于第i-1次
• 内循环下界为w[i]：若c < w[i]当前物品放不进去了

初始化

• 无必须填满背包，只希望总价值最大：dp[0..C]=0
• 必须填满背包（暂未碰到）：dp[0]= 0，其余dp[1..C]=-float('inf')