视频字幕
背包问题是动态规划中的经典问题。给定一个背包和若干物品,每个物品都有重量和价值,目标是在不超过背包容量的前提下,选择物品使总价值最大。背包问题主要分为两种:01背包和完全背包。
01背包问题中,每种物品只有一件,对于每个物品只能选择放入或不放入,不能重复选取。状态转移方程为dp[j]等于dp[j]和dp[j减去物品重量]加上物品价值的最大值。关键在于内层循环必须逆序遍历,这样可以保证每个物品只被考虑一次。
完全背包问题中,每种物品有无限件,可以重复选取同一物品。状态转移方程形式相同,但关键区别在于内层循环必须正序遍历。这样可以确保在计算当前状态时,已经考虑了可能多次选择当前物品的情况,从而实现物品的重复选取。
循环顺序是两种背包问题的关键差异。01背包使用逆序循环,从大到小遍历容量,这样可以避免在同一轮中重复选取同一物品。完全背包使用正序循环,从小到大遍历容量,这样可以在同一轮中多次选取同一物品,实现重复选取的效果。
总结两种背包问题的核心差异:01背包每种物品只有一件,使用逆序循环避免重复选取,适用于选课、投资等场景。完全背包每种物品有无限件,使用正序循环允许重复选取,适用于硬币找零、资源分配等场景。理解这些差异有助于在实际问题中选择合适的算法。