视频字幕
欢迎来到C++背包问题的讲解！背包问题是计算机科学中的经典动态规划问题。想象你有一个固定容量的背包，比如容量为10公斤，还有一系列物品可以选择。每个物品都有自己的重量和价值，比如物品A重2公斤价值3，物品B重3公斤价值4，物品C重4公斤价值5。我们的目标是选择哪些物品放入背包，使得总重量不超过背包容量，同时总价值最大。
为了解决背包问题，我们使用动态规划的思路。首先定义状态：dp[i][j]表示考虑前i个物品，在背包容量为j时能获得的最大价值。然后确定状态转移方程：对于每个物品，我们有两种选择，要么不放入背包，此时dp[i][j]等于dp[i-1][j]；要么放入背包，前提是容量足够，此时dp[i][j]等于dp[i-1][j-weight[i]]加上当前物品的价值。我们取这两种情况的最大值。
现在让我们看看C++的具体实现。首先包含必要的头文件，定义背包函数，参数包括物品重量数组、价值数组和背包容量。创建二维DP表，大小为n+1乘以capacity+1。然后用双重循环填充DP表，外层循环遍历物品，内层循环遍历容量。在循环中实现状态转移方程的逻辑判断，如果当前物品重量小于等于当前容量，就比较放入和不放入的价值，取最大值。最后返回DP表右下角的值，即为最优解。
让我们用具体例子演示算法执行过程。假设有三个物品：A重量2价值3，B重量3价值4，C重量4价值5，背包容量为5。首先初始化DP表的第一行和第一列为0。然后逐行逐列填充表格，对每个位置应用状态转移方程。当考虑物品A时，在容量2以上的位置填入价值3。考虑物品B时，比较不放B和放B的价值。最终在右下角得到最优解7，表示选择物品A和B的组合。
最后我们来分析算法的复杂度。时间复杂度为O(n乘以W)，其中n是物品数量，W是背包容量，因为我们需要填充整个DP表。空间复杂度也是O(n乘以W)，用于存储二维DP表。在实际应用中，可以使用滚动数组将空间复杂度优化到O(W)。背包问题在现实中有广泛应用，比如资源分配优化、投资组合选择、货物装载等问题。掌握这个经典算法对理解动态规划思想非常重要。