## 01背包描述 [01背包详解](https://kernelcode.cn/article/152) ``` 【问题描述】 有 N 件物品和一个容量为 W 的背包。 第 i 件物品的重量是 weight[i]，价值是 value[i]。 每件物品只有一件，可以选择放或不放。 求将哪些物品装入背包可使总价值最大。 【约束条件】 - 每个物品只能选 0 次或 1 次（选或不选） - 物品不可分割 - 背包容量有限 ``` ## 完全背包描述 ``` 【问题描述】 有 N 种物品和一个容量为 W 的背包。 第 i 种物品的重量是 weight[i]，价值是 value[i]。 每种物品都有无限件可用。 求将哪些物品装入背包可使总价值最大。 【约束条件】 - 每个物品可以选无限次（0, 1, 2, ...） - 物品不可分割 - 背包容量有限 ``` ## 记忆口诀 **方程一样，顺序不同。** 0-1 倒序 → 保证只用一次 完全正序 → 允许重复使用 求组合 → 先物品后容量 求排列 → 先容量后物品 ## 模版代码 `和01背包对比记忆` 【遍历顺序】核心区别 ``` for i in range( n ): # !important:完全背包限定( 正序遍历重量 ) for j in range( weights[ i ], w + 1 ): dp[ j ] = max( dp[ j - weights[ i ] ] + values[ i ], dp[ j ] ) ``` 【为什么容量必须正序】 ``` 正序允许每个物品被多次选取。 当 j 从小到大遍历时，dp[j - weight[i]] 可能已经包含了物品 i， 这样 dp[j] 就可以在选过物品 i 的基础上再选一次， 恰好符合完全背包每个物品可以选多次的要求。 ``` 【完全背包模版】 ```python # w 背包最大可装重量 # weights[ i ] 每个物品的重量 # values[ i ] 每个物品的价值 def complete_backpack( w, weights, values ): n = len( weights ) # dp[ i ] 表示容积为i的最大价值 dp = [ 0 for _ in range( w + 1 ) ] for i in range( n ): # !important:完全背包限定( 正序遍历重量 ) for j in range( weights[ i ], w + 1 ): # 可以选中或不选 两者价值取最大 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 complete_backpack( w, weights, values ) print( main() ) ```