371，背包问题系列之-基础背包问题
描述
背包问题是动态规划中最经典的一道算法题。背包问题的种类比较多，我们先来看一个最简单的背包问题-基础背包。他是这样描述的。
有N件物品和一个容量为V的包，第i件物品的重量是w[i]，价值是v[i]，求将哪些物品装入背包可使这些物品的重量总和不能超过背包容量，且价值总和最大。我们先来举个例子分析一下
举例分析
假设我们背包可容纳的重量是4kg，有3样东西可供我们选择，一个是高压锅有4kg，价值300元，一个是风扇有3kg，价值200元，最后一个是一双运动鞋有1kg，价值150元。问要装哪些东西在重量不能超过背包容量的情况下价值最大。如果只装高压锅价值才300元，如果装风扇和运动鞋价值将达到350元，所以装风扇和运动鞋才是最优解，我们来画个图分析一下
我们上面选择的顺序是：运动鞋→高压锅→风扇，如果我们改变选择的顺序，结果会不会改变，比如我们选择的顺序是：风扇→运动鞋→高压锅，我们还是来画个图看一下
我们发现无论选择顺序怎么改变都不会改变最终的结果。
数据测试：
我们就用上面的图形分析的数据来测试一下，看一下最终结果
1public static void main(String[] args) {
2 System.out.println("最终结果是：" + packageProblem1());
3}
4
5public static int packageProblem1() {
6 int packageContainWeight = 4;//包最大可装重量
7 int[] weight = {1, 4, 3};//3个物品的重量
8 int[] value = {150, 300, 200};//3个物品的价值
9 int[][] dp = new int[weight.length + 1][packageContainWeight + 1];
10 for (int i = 1; i <= value.length; i++) {
11 for (int j = 1; j <= packageContainWeight; j++) {
12 if (j >= weight[i - 1]) {
13 dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i - 1]] + value[i - 1]);
14 } else {
15 dp[i][j] = dp[i - 1][j];
16 }
17 }
18 }
19 Util.printTwoIntArrays(dp);//这一行仅做打印观测数据，也可以去掉
20 return dp[weight.length][packageContainWeight];
21}和我们上面分析的完全一致。（为了测试方便，这里的所有数据我都是写死的，我们也可以把这些数据提取出来，作为函数参数传进来。)
空间优化：
其实这题还可以优化一下，这里的二维数组我们每次计算的时候都是只需要上一行的数字，其他的我们都用不到，所以我们可以用一维空间的数组来记录上一行的值即可，但要记住一维的时候一定要逆序，否则会导致重复计算。我们来看下代码
1public static int packageProblem2() {
2 int packageContainWeight = 4;
3 int[] weight = {1, 4, 3};
4 int[] value = {150, 300, 200};
5 int[] dp = new int[packageContainWeight + 1];
6 for (int i = 1; i <= value.length; i++) {
7 for (int j = packageContainWeight; j >= 1; j--) {
8 if (j - weight[i - 1] >= 0)
9 dp[j] = Math.max(dp[j], dp[j - weight[i - 1]] + value[i - 1]);
10 }
11 Util.printIntArrays(dp);
12 System.out.println();
13 }
14 return dp[packageContainWeight];
15}
注意：
我们看到第7行在遍历重量的时候采用的是逆序的方式，因为第9行在计算dp[j]的值的时候，数组后面的值会依赖前面的值，而前面的值不会依赖后面的值，如果不采用逆序的方式，数组前面的值更新了会对后面产生影响。
C++：
1#include<iostream>
2#include <algorithm>
3
4using namespace std;
5
6int main()
7{
8 int weight[] = { 1,4,3 };
9 int value[] = {150, 300, 200 };
10 int packageContainWeight = 4;
11 int dp[4][5]= { { 0 } };
12 for (int i = 1; i <4 ; i++)
13 {
14 for (int j = 1; j < 5; j++)
15 {
16 if (j >= weight[i - 1])
17 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i - 1]] + value[i - 1]);
18 else
19 dp[i][j] = dp[i - 1][j];
20 }
21 }
22
23 for (int i = 0; i < 4; i++)
24 {
25 for (int j = 0; j < 5; j++)
26 {
27 cout << dp[i][j] << ' ';
28 }
29 cout << endl;
30 }
31
32 return 0;
33}
3405运行结果递归写法：
除了上面的两种写法以外，我们还可以使用递归的方式，代码中有注释，有兴趣的可以自己看，就不在详细介绍。
1int[] weight = {1, 4, 3};//3个物品的重量
2int[] value = {150, 300, 200};//3个物品的价值
3
4// i：处理到第i件物品，j可容纳的重量
5public int packageProblem3(int i, int j) {
6 if (i == -1)
7 return 0;
8 int v1 = 0;
9 if (j >= weight[i]) {//如果剩余空间大于所放的物品
10 v1 = packageProblem3(i - 1, j - weight[i]) + value[i]; //选第i件
11 }
12 int v2 = packageProblem3(i - 1, j);//不选第i件
13 return Math.max(v1, v2);
14}
长按上图，识别图中二维码之后即可关注。
如果喜欢这篇文章就点个"在看"吧