视频字幕
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。这样逐步填充整个表格。