动态规划算法之0-1背包问题

骑猪看日落 2023-07-15 05:54 47阅读 0赞

**动态规划算法介绍**  
（1） 动态规划(Dynamic Programming)算法的核心思想是：将大问题划分为小问题进行解决，从而一步步获取最优解的处理算法  
（2）动态规划算法与分治算法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解  
（3）与分治法不同的是，适合于用动态规划求解的问题，经分解得到的子问题往往不是互相独立的 ( 即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解 )  
（4）动态规划可以通过填表的方式来逐步推进，得到最优解

**0-1背包问题的动态规划图解**

（1）0-1背包问题描述：

有一个背包，容量为4，现有如下物品

![20200315171700922.png][]

（1.1）要求达到的目标为 装入背包中的物品的总价值最大，并且物品的总重量不超出背包的容量

（1.2）要求 装入的物品不能重复

（2）思路分析

利用动态规划来解决,每次遍历到的第 i 个物品，根据 weight\[i\] 与 value\[i\] 来确定是否需要将该物品放入背包中。即对于给定的 n个物品，设 weight\[i\]、value\[i\] 分别为第 i 个物品的重量与价值，m 为背包的容量。再令 v\[i\]\[j\] 表示在前 i 个物品中进行组合后装入容量为 j 的背包中的最大价值。则有下面的结果：  
(2.1) v\[0\]\[i\] = v\[i\]\[0\]=0; // 表示 填入表 第一行和第一列都是 0  
(2.2) 当 weight\[i\] > j 时，v\[i\]\[j\] = v\[i-1\]\[j\]; // 当准备加入的新增的商品的重量大于当前背包的容量时，就直接使用上一个单元格的装入策略  
(2.3) 当 j >= weight\[i-1\] 时： v\[i\]\[j\]=max\{v\[i-1\]\[j\], value\[i\] + v\[i-1\]\[j-weight\[i\]\]\} // 当准备加入的新增的商品的重量小于或者等于当前背包的容量时,使用的装入策略，各部分说明如下  
v\[i-1\]\[j\]： 就是上一个单元格的装入的最大价值  
value\[i\] : 表示当前商品的价值  
v\[i-1\]\[j-weight\[i\]\] ： 装入前 i-1 个商品，到剩余背包容量 j-weight\[i\] 的最大价值  
当 j >= weight\[i\] 时： v\[i\]\[j\] = max\{v\[i-1\]\[j\], value\[i\]+v\[i-1\]\[j-weight\[i\]\]\} ;

（3）如下填表方式，逐步推导，得到最优解

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NjQ1MDk5_size_16_color_FFFFFF_t_70][]

**代码实现**

package com.zzb.algorithm.dynamic;
    
    /**
     * 动态规划算法
     * 应用实例：0-1背包问题（限制每个物品要么拿（1个），要么不拿（0个））
     */
    public class KnapsackProblem {
    	public static void main(String[] args) {
            // 每个物品的重量
    		int[] weight = {1, 2, 4};
    		// 每个物品的价值
    		int[] value = {40, 30, 10};
    		// 背包的容量
    		int m = 4;
    		// 物品的个数
    		int n = value.length;
    
            // v[i][j] 表示在前i个物品中进行组合后装入容量为j的背包中的最大价值
    		int[][] v = new int[n+1][m+1];
    		// 记录放入物品的情况
    		int[][] path = new int[n+1][m+1];
    
    		// 二维数组 int[][] v 的第一行与第一列的初始化
    		// 可以不处理，默认就是0
    		for(int i = 0; i < v[0].length; i++) {
    			v[0][i] = 0;
    		}
    		for(int i = 0; i < v.length; i++) {
    			v[i][0] = 0;
    		}
    
    		// 实现 0-1背包 中物品的最大值
    		// i 可理解为：第i个物品（行代表具有重量与价值的不用物品）
    		// j 可理解为：背包的不同容量（列代表不同容量的背包）
    		// v[i][j] 表示在前i个物品中进行组合后装入容量为j的背包中的最大价值
    		for(int i = 1; i < v.length; i++) {  // 循环取出每一个物品
    			for(int j = 1; j < v[0].length; j++) { // 前i个物品在不用容量j的背包下的最大价值
    				// weight[i-1] value[i-1] 解释：i的初始值为1（i= 1），代表第一个物品，但是在weight[]中
    				// 第一个物品的下标索引为0，索引要 i - 1 指向第一个物品
    				if(weight[i-1] > j) { // 第i个物品的重量大于当前背包的容量j
    					v[i][j] = v[i-1][j];
    				} else {
    					if(v[i-1][j] < value[i-1] + v[i-1][j-weight[i-1]]) {
    						v[i][j] = value[i-1] + v[i-1][j-weight[i-1]];
    						// 记录第i个物品放入背包的情况
    						path[i][j] = 1;
    					} else {
    						v[i][j] = v[i-1][j];
    					}
    				}
    			}
    		}
    
    		// 不用容量的背包中物品的最大价值
    		for(int i =0; i < v.length; i++) {
    			for(int j = 0; j < v[i].length; j++) {
    				System.out.print(v[i][j] + "\t");
    			}
    			System.out.println();
    		}
    		/*0	0	0	0	0
    		0	40	40	40	40
    		0	40	40	70	70
    		0	40	40	70	70*/
    
    		System.out.println("============================");
    
    		for(int i = 0; i < path.length; i++) {
    			for(int j = 0; j < path[i].length; j++) {
    				if(path[i][j] == 1) {
    					System.out.println("第 " + i + " 个物品放入了背包");
    				}
    			}
    		}
    		/*第 1 个物品放入了背包
    		第 1 个物品放入了背包
    		第 1 个物品放入了背包
    		第 1 个物品放入了背包
    		第 2 个物品放入了背包
    		第 2 个物品放入了背包*/
    
    		System.out.println("============================");
    
    		// i j 初始化指向二维数组v[][]的最后一个单元格，即为0-1背包问题的最优解（背包中物品的最大价值）
    		// 循环判断第i个物品是否放入了容量为j的背包中（path[i][j] == 1），
    			// 如果放入了，则求出背包的剩余容量（j -= weight[i-1]），继续判断第i-1（i--）个物品是否放入容量为j的背包中
    			// 如果没放入，则判断前一个物品（i--）是否放入了容量为j的背包中
    		// weight[i-1] 解释：i的初始值为i = path.length - 1（i=3），代表最后一个物品，但是在weight[]中
    		// 最后一个物品的下标索引为2，索引要 i - 1 指向最后一个物品
    		int i = path.length - 1;
    		int j = path[0].length - 1;
    		while(i > 0 && j > 0 ) {
    			if(path[i][j] == 1) {
    				System.out.println("第 " + i + " 个物品放入了背包，" + "其重量为 " + weight[i-1] + "，价值为 " + value[i-1]);
    				j -= weight[i-1];
    			}
    			i--;
    		}
    		/*第 2 个物品放入了背包，其重量为 2，价值为 30
    		第 1 个物品放入了背包，其重量为 1，价值为 40*/
    	}
    }

[20200315171700922.png]: /images/20230528/079ba556080445e88957aae3b6559714.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NjQ1MDk5_size_16_color_FFFFFF_t_70]: /images/20230528/64fc5aa0ec2c4763bec27f275d191eb2.png