背包问题
背包问题简介
背包问题的定义
背包问题：背包问题是线性 DP 问题中一类经典而又特殊的模型。背包问题可以描述为：给定一组物品，每种物品都有自己的重量、价格以及数量。再给定一个最多能装重量为 WWW 的背包。现在选择将一些物品放入背包中，请问在总重量不超过背包载重上限的情况下，能装入背包的最大价值总和是多少？
根据物品限制条件的不同，背包问题可分为：0-1 背包问题、完全背包问题、多重背包问题、分组背包问题，以及混合背包问题等
背包问题的暴力解题思路
背包问题的暴力解题思路比较简单。假设有 n 件物品。先枚举出这 n 件物品所有可能的组合。然后再判断这些组合中的物品是否能放入背包，以及是否能得到最大价值。这种做法的时间复杂度是 \(O\left(2^{n}\right)\)
背包问题暴力解法的时间复杂度是指数级别的，可以利用动态规划算法减少一下时间复杂度