背包问题之-基础背包问题

描述

背包问题是动态规划中最经典的一道算法题。背包问题的种类比较多，我们先来看一个最简单的背包问题-基础背包。他是这样描述的。

有N件物品和一个容量为V的包，第i件物品的重量是w[i]，价值是v[i]，求将哪些物品装入背包可使这些物品的重量总和不能超过背包容量，且价值总和最大。我们先来举个例子分析一下

举例分析

假设我们背包可容纳的重量是4kg，有3样东西可供我们选择，一个是高压锅有4kg，价值300元，一个是风扇有3kg，价值200元，最后一个是一双运动鞋有1kg，价值150元。问要装哪些东西在重量不能超过背包容量的情况下价值最大。如果只装高压锅价值才300元，如果装风扇和运动鞋价值将达到350元，所以装风扇和运动鞋才是最优解，我们来画个图分析一下

1

结合图形分析

2

改变选择的顺序

我们上面选择的顺序是：运动鞋高压锅风扇，如果我们改变选择的顺序，结果会不会改变，比如我们选择的顺序是：风扇运动鞋高压锅，我们还是来画个图看一下

我们发现无论选择顺序怎么改变都不会改变最终的结果。

数据测试：

我们就用上面的图形分析的数据来测试一下，看一下最终结果

3

运行结果

和我们上面分析的完全一致。（为了测试方便，这里的所有数据我都是写死的，我们也可以把这些数据提取出来，作为函数参数传进来。)

空间优化：

其实这题还可以优化一下，这里的二维数组我们每次计算的时候都是只需要上一行的数字，其他的我们都用不到，所以我们可以用一维空间的数组来记录上一行的值即可，但要记住一维的时候一定要逆序，否则会导致重复计算。我们来看下代码

注意：

我们看到第7行在遍历重量的时候采用的是逆序的方式，因为第9行在计算dp[j]的值的时候，数组后面的值会依赖前面的值，而前面的值不会依赖后面的值，如果不采用逆序的方式，数组前面的值更新了会对后面产生影响。

4

运行结果

C++：

5

运行结果

递归写法：

除了上面的两种写法以外，我们还可以使用递归的方式，代码中有注释，有兴趣的可以自己看，就不在详细介绍。

如果喜欢这篇文章就点个"在看"吧