前言

本文是最入门级别的动态规划背包问题的解题过程，帮助小白理解动态规划背包问题的解题思路和转化为代码的过程。

动态规划背包问题是什么？

一个背包只能装下5kg物品；

现有：

物品一：1kg价值6元，

物品二：2kg价值10元，

物品三：3kg价值15元，

物品四：4kg价值12元。

问：怎么装，价值最大化？ （每样物品只有一件，且每个物品不可拆分）

动态规划解题转代码

动态规划的解题套路千千万，但都是离不开穷举+if装这个物品会怎样else不装会怎样，最终比较一下结果哪条路得到价值最大，就是哪条路。

我选个最好理解的。

总体思路是：背包总共5kg分成1kg1kg的作为最外层循环（穷举的根），每次都取最优。

第一步：拆包填表格

如何填写表格？把当前状态（背包为某kg）下，最多能装的价格填进去！

1）横着看第一行：当背包1kg时，加入物品1是多少¥，就填进去；当背包是2kg，加入物品一是多少¥，就填进去......以此类推

2）横着看第二行：当背包1kg时，加不进去物品二，那当背包1k时候利益最大就是¥6；当背包2kg时候加物品二是¥10，比加物品一的¥6多，所以利益最大是放二物品 ；当背包是3kg时候，在原有物品一的基础上，还可以再加物品二，价值就变为¥6+¥10=¥16元，以此类推。

3）横着看第三行：1kg放不下；2kg也装不下，取之前最大利益10¥；3kg可以装下，但是3kg全装物品三价值为¥15，但是之前两物品可以得到¥16，那么还是之前的落下来¥16。4kg时候，装3kg物品三还剩1kg装下物品一后二者之和为¥21，所以最大值取物品三加物品一的。

4）横着看第四行：同上道理

以上，物品加完，价值最大在哪里？在表格最右下角！

这个思路，和穷举四个物品432*1=24种结果区别在哪里？这种方式相当于穷举每次都有最优解！

这就是状态转移方程： 就是拿装和 不装 每次都和上面的比较，大了就装，小了就不装！

第二步：转为代码

以上这拆包填表过程转为伪代码是什么？

一、首先看空表格：即初始化代码

1、最基础的准备：

        // 物品价值

		int value[] = { 6, 10, 15, 12 };

		// 物品重量

		int weight[] = { 1, 2, 3, 4 };

		// 背包总容量

		int bagWeight = 5;

		// 物品总数量

		int num = 4;

2、准备下面这个表格：二维数组

        // 表格内容:第一个[]表示行（坐标） 第二个[]表示列 （坐标）

        // [][] 两个坐标定位出哪个表格，dp[][]取出的就是最大价值金额

        // 防止越界可以加个1，横是待装物品个数，竖是被拆分的背包重量

		int dp[][] = new int[num + 1][bagWeight + 1];

 二、看怎么循环填表格

1、按行循环

// 最外层循环即 表格横向有几行就循环几次

for (int i = 1; i <= num; i++) {


}

2、每行里按列循环

// 被拆分的背包 单行从左到右依次循环，有几列循环几次

for (int everyBagWeight = 1; everyBagWeight <= bagWeight; everyBagWeight++) {


}

3、表格里填入多少如何判断 

1）能装下这个物品：

// if 物品重量 小于 当前拆分后背包的重量 就是能装

// weight[i是最外层的循环（有几个物品i就等于几，i-1下标的值就是第几个物品的重量值）]

if (weight[i - 1] <= everyBagWeight) {


}

1-1）能装下这个物品，装还是不装

// 能装就计算装之后和装之前 哪个是最大价值

dp[i][everyBagWeight] = Math.max(

	// 装之后

	value[i - 1] + dp[i - 1][everyBagWeight - weight[i - 1]],

	// 装之前

	dp[i - 1][everyBagWeight]

);

 这里很晕举个例子说明，以红色格子为例子：

// 红色格子能装就计算装之后和装之前 哪个是最大价值

//给纵坐标4，横坐标5的格子赋值

dp[i=4 ][everyBagWeight = 5kg] = 


    Math.max(

	    // 装之后～～～～～～～～～～～～～～～～

        //value[i-1=3]是第四个物品的价值 = 12¥

        //dp[i-1=3]是纵坐标是[3]，

        //[5 - weight[3]]即（总重量）减掉（当前物品四的weight[3]=4kg ）=1kg

        //dp[3][1]是纵坐标是[3]，横坐标为[1]即粉色格子值¥6

        //所以装之后总价值为¥12+¥6=¥18


	    value[i-1] + dp[i - 1][everyBagWeight - weight[i - 1]],//=¥18


	    //-----------------------------------------------------

        // 装之前～～～～～～～～～～～～～～～

        //dp[i-1=3][everyBagWeight = 5]

        //纵坐标是3 横坐标是5 即是绿色格子的值 ¥25

	    dp[i - 1][everyBagWeight]

    );

//取最大：25>18所以是赋值25

2）装不下

	            // 装不下 就是绿色格子直接赋值上面的价值

				} else {

					dp[i][everyBagWeight] = dp[i - 1][everyBagWeight];

				}

 三、输出结果（最大价值）

//表格右下角就是结果

System.out.print(dp[num][bagWeight]);

 第三步：完整代码

public class Bag {

	public static void main(String[] args) {

		// 物品价值

		int value[] = { 6, 10, 15, 12 };

		// 物品重量

		int weight[] = { 1, 2, 3, 4 };

		// 背包总容量

		int bagWeight = 5;

		// 物品总数量

		int num = 4;

		// 表格内容:第一个[]表示价值 第二个[]表示重量？？

		int dp[][] = new int[num + 1][bagWeight + 1];


		// 每次加物品 最外层循环即表格横向有几行就循环几次

		for (int i = 1; i <= num; i++) {


			// 被拆分的背包 单行从左到右依次循环，有几列循环几次

			for (int everyBagWeight = 1; everyBagWeight <= bagWeight; everyBagWeight++) {


				// 尝试装物品

				// if装 ： 物品重量 小于 当前拆分后背包的重量

				if (weight[i - 1] <= everyBagWeight) {

					// 能装就计算装之后和装之前 哪个是最大价值

					dp[i][everyBagWeight] = Math.max(

							// 装之后

							value[i - 1] + dp[i - 1][everyBagWeight - weight[i - 1]],

							// 装之前

							dp[i - 1][everyBagWeight]);


					// 装不下 就是上面的价值

				} else {

					dp[i][everyBagWeight] = dp[i - 1][everyBagWeight];

				}

			}

		}

		//表格右下角就是结果

		System.out.print(dp[num][bagWeight]);

	}


}

 动态规划写出路径

以上问题，我们只是计算出了最大价值是多少，那如果需要输出拿了哪个物品呢？

我们只需要把最右列倒着遍历，即背包重量最大时的容量都装了哪些物品，即可

 拿这道题举例子，有如下这么几种情况：

1）如果加了物品四和没加物品四是一样的，代表物品四根本没有加入。即dp[4][5] ==dp[3][5]

2）如果加了物品三和没加物品三是不一样的，代表物品三是加入了的，需要输出！

3）因为我们表格横纵坐标都是从1开始的，所以遍历不到，最后补上就可以。

        // 具体的物品输出，只需要遍历最后一列即可（从右下角表格向上走）

		for (int j = num; j > 1; j--) {

			if (dp[j][bagWeight] == dp[j - 1][bagWeight]) {

				// 该物品加入，与没加入没有差别，意味着该物品没有加入，即不用输出

			} else {

				// 该物品被加入了，输出即可

				System.out.println("加入物品" + j + ":重量=" + weight[j - 1] + ";价值=" + value[j - 1]);

				bagWeight = bagWeight - weight[j - 1];

			}

		}

		// 如果背包不等于0，就要把最后一个商品加进来

		if (bagWeight != 0) {

			System.out.println("最后加入物品" + 1 + ":重量=" + weight[0] + ";价值=" + value[0]);

		}

以上就是入门全部过程～