01背包问题是什么？
编辑：自学文库
时间：2024年03月09日
问题的名称来源于每件物品只有选取或不选取两种选择，即0或1。
具体而言，给定n个物品，每个物品有一个重量wi和价值vi。
背包的容量为W。
要求在背包容量限制下，选择哪些物品放入背包，使得背包中物品的总价值最大。
解决该问题的一种常用方法是使用动态规划。
定义一个二维数组dp[i][j]，表示在前i个物品中，背包容量为j时的最大价值。
则存在以下状态转移方程： 当i=0或j=0时，dp[i][j] = 0； 当j=wi时，dp[i][j] = max(dp[i-1][j], dp[i-1][j-wi]+vi)； 最终，dp[n][W]即为问题的最优解，表示在n个物品中，背包容量为W时的最大价值。
通过动态规划求解01背包问题，可以有效地解决在背包容量限制下选择物品的问题，找到使得背包价值最大化的解。