视频字幕
01背包问题是计算机科学中的经典问题。我们有一个容量有限的背包和一组物品,每个物品都有自己的重量和价值。我们的目标是在不超过背包容量的前提下,选择一些物品放入背包,使得总价值最大。这里的关键是每个物品只能选择放入或不放入,不能部分放入。
动态规划是解决01背包问题的经典方法。我们定义一个二维数组dp,其中dp[i][j]表示考虑前i个物品,在背包容量为j时能获得的最大价值。状态转移方程是:对于每个物品,我们可以选择放入或不放入。如果不放入,价值等于dp[i-1][j];如果放入,价值等于dp[i-1][j-重量] 加上当前物品的价值。我们取两者的最大值。
现在我们来演示如何填充DP表格。首先初始化第一行和第一列为0,表示没有物品或容量为0时的情况。然后逐个考虑每个物品。对于物品1,重量为3,价值为4,当容量大于等于3时,我们可以选择放入。比如在容量为4时,不选择物品1的价值是0,选择物品1的价值是4,所以我们选择4。这样逐步填充整个表格。