有n件物品和一个最多能背重量为`w`的背包。第i件物品的重量是`weight[i]`，得到的价值是`value[i]`。每件物品只能用一次，求解将哪些物品装入，使得背包里物品价值总和最大。 ## 01背包分析 **暴力解法**：每个物品有`选和不选`两种状态，所以可以通过回溯探索出所有情况。取所有情况中，满足背包容积的最大价值即可。显然，时间复杂度是指数级的`O(2^n)`。 **如何优化？** 分析如下： - 返回的是装入物品背包价值总和最大，该价值的组成是物品的`选或不选`组成的结果。 - ``` - 单个物品来看， 如果物品重量大于背包`不选`， 反之`选择`; - 两个物品来看， 物品1有选和不选两种情况， 物品2也有选和不选两种情况，那么怎么排列呢？ 物品选或不选，直接取决于背包剩余容量。 若容量足够才有选和不选两种状态， 若容量不足只能不选。 已知，物品1的状态是选或不选，姑且不论是哪种， 记最大价值为x (可能因为容量不足没选， 也可能容量足够就选择了， 当然容量足够也可以选择不选 )。 来看物品2：若不选，则价值就是x。 若选择，需要考虑容积是否足够，这样就需要知道 w - weight[2]位置的最大价值是什么， 最大价值 = max( x, w - weight[2]价值 + value[2] )。 所以很明显，需要记录每处w的最大价值。所以01背包的模版就有了。 ``` ```python # w 背包最大可装重量 # weights[ i ] 每个物品的重量 # values[ i ] 每个物品的价值 def backpack_01( w, weights, values ): n = len( weights ) # dp[ i ] 表示容积为i的最大价值 dp = [ 0 for _ in range( w + 1 ) ] """ --- 实现递推 --- Q:先遍历背包重量,还是先遍历物品? A:先遍历物品再遍历容量。 Q:为什么是这样的遍历顺序? A:先用i个物品去填充1~w的背包,就相当于知道i个物品在1~w的背包中的最大价值。 当再加入第i+1个物品时,借助前i个物品记录的最大价值,可以很容易的推出 i+1个物品填充的最大价值。 Q:既然如此,是否是需要初始化1个物品装1~w背包的最大价值? A:实际上是需要的,但是换个角度想,0个物品装1~w背包,最大价值全是0,其实就是初始化了。 --- !important: 还有一个细节问题: w必须是倒序遍历的。 for i in range( n ): for j in range( 1, w + 1 ): # 正序遍历容量 这是完全背包的遍历顺序，不是 0-1 背包。 0-1 背包要求每个物品只能选一次，因此容量必须倒序遍历： for i in range( n ): for j in range( w, weights[i] - 1, -1 ): # 倒序遍历容量 正序遍历时： 当处理物品 i，更新 dp[j] 时， dp[j - weights[i]] 可能已经包含了物品 i 的价值（本轮刚更新的）， 导致物品 i 被多次选取。 """ for i in range( n ): # 边界weights[ i ] - 1 <=> j = weights[ j ] >= 0 # !important:01背包限定( 倒序遍历重量 ) for j in range( w, weights[ i ] - 1, -1 ): # 可以选中或不选 两者价值取最大 # dp[ j ]未更新前 就是i-1个物品装j的最大容量 dp[ j ] = max( dp[ j - weights[ i ] ] + values[ i ], dp[ j ] ) return dp[ -1 ] def main(): n, w = map( int, input().split() ) weights = [ 0 for _ in range( n ) ] values = [ 0 for _ in range( n ) ] for i in range( n ): weights[ i ], values[ i ] = map( int, input().split() ) return backpack_01( w, weights, values ) print( main() ) ```