背包问题（贪心）& 二维01背包问题

背包问题（贪心）

最优装载问题

题目描述

有n件物品和一个最大承重为w 的背包。第i件物品的重量是weight[i]，每件只能用一次，求装入背包的最多物品数量。

题目分析

• 因为我们只要求装入物品的数量，所以装重的显然没有装轻的划算。
• 因此将数组weight[i]按从小到大排序，依次选择每个物品，直到装不下为止，就可以得到装入背包的最多物品数量。

代码

public static int stone(int n, int w, int[] weight) {
	Arrays.sort(weight);    //将weight数组从小到大排序
    int max = 0;
    int num = 0;
    for(int i = 0; i < n; i++) {
        if(max + weight[i] <= w){
        max += weight[i];
           num += 1;
       }
    }
    return num;
}

01背包问题

与上面的贪心背包问题而言，贪心背包问题中物品的价值就是它的重量。
先前题主做的拿金币问题，也可以说是一道背包问题，不过其中背包的容量是无限的，物品就是金币。

题目描述

有n件物品和一个最大承重为bagweight 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。
卡码网第46题

题目分析

显然也是一道动态规划题，也就是说背包问题是动态规划问题的子集，当然这不重要。
我们先观察一下背包的属性：

• 当前装入物品的个数
• 当前装入物品的总重量（容量）
• 当前装入物品的总价值
• 关键在当前重量的基础上使得价值最高

注：下文基本转述于代码随想录的网站，只加了部分自己的理解

可转到代码随想录的网站去更深刻地理解01背包知识
代码随想录的链接：戳这里进入

老规矩动归五部曲

定义dp数组

定义一个二维数组dp[i][j]，将i定义为当前放入了多少个物品，表示

• 从下标为[0-i]的物品里任意取，
• 放进容量为j的背包，
• 价值总和最大是多少。（dp数组的值）

确定dp数组递归公式

在决定是否放入第i个物品时，显然有两种情况

• 要么不满足放入第i个物品的情况（当物品i的重量大于背包j的重量时，物品i无法放进背包中）

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

• 要么满足放入第i个物品的情况，此时比较放入前后的价值总和，判断是否要放入。

dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j - weight[i] + value[i];

dp数组的初始化

从dp[i][j]出发，

1. 当背包容量j为0的时候，则放不下任何物品，背包中价值总和为0；

for (int i = 0 ; i < weight.length; i++) { 
    dp[1][0] = 0;

再看其他情况。

2. 因为递推公式dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
   当中含有i-1，即我们在遍历时肯定从i=1的时候开始遍历，那么物品为0的时候就一定要初始化。
   此时考虑是否可以加入物品0，
   • 当 j < weight[0]的时候，dp[0][j] 为 0
   • 当j >= weight[0]时，dp[0][j] 为value[0]

for (int j = 0 ; j < weight[0]; j++)   // 如果把dp数组预先初始化为0了，这一步可以省略
    dp[0][j] = 0;
    
for (int j = weight[0]; j <= bagweight; j++) 
    dp[0][j] = value[0];

3. 其他位置可以任意初始化，但是一开始就统一把dp数组统一初始为0，更方便一些。

dp数组的遍历顺序

显然有两个遍历的维度：物品与背包容量
先遍历物品，或先遍历背包容量呢。
这里两种遍历顺序都可以，是因为，递推的方向分别是由上的与由左的到，而两个遍历顺序都是会先得到递推公式需要的旧数据，因此不影响。

//先遍历物品
for(int i = 1; i < weight.size(); i++) { // 遍历物品
    for(int j = 0; j <= bagweight; j++) { // 遍历背包容量
        if (j < weight[i]) dp[i][j] = dp[i - 1][j];
        else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

    }
}
//先遍历背包容量
for(int j = 0; j <= bagweight; j++) { // 遍历背包容量
    for(int i = 1; i < weight.size(); i++) { // 遍历物品
        if (j < weight[i]) dp[i][j] = dp[i - 1][j];
        else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
    }
}

举例说明dp数组

代码

import java.util.Arrays;

public class BagProblem {
    public static void main(String[] args) {
        int[] weight = {1,3,4};//这里是代码随想录的示范用例
        int[] value = {15,20,30};
        int bagSize = 4;
        testWeightBagProblem(weight,value,bagSize);
    }

    public static void testWeightBagProblem(int[] weight, int[] value, int bagSize){

        // 创建dp数组
        int goods = weight.length;  // 获取物品的数量
        int[][] dp = new int[goods + 1][bagSize + 1];  // 给物品增加冗余维，i = 0 表示没有物品可选

        // 初始化dp数组，默认全为0即可
        // 填充dp数组
        for (int i = 1; i <= goods; i++) {
            for (int j = 1; j <= bagSize; j++) {
                if (j < weight[i - 1]) {  // i - 1 对应物品 i
                    /**
                     * 当前背包的容量都没有当前物品i大的时候，是不放物品i的
                     * 那么前i-1个物品能放下的最大价值就是当前情况的最大价值
                     */
                    dp[i][j] = dp[i - 1][j];
                } else {
                    /**
                     * 当前背包的容量可以放下物品i
                     * 那么此时分两种情况：
                     *    1、不放物品i
                     *    2、放物品i
                     * 比较这两种情况下，哪种背包中物品的最大价值最大
                     */
                    dp[i][j] = Math.max(dp[i - 1][j] , dp[i - 1][j - weight[i - 1]] + value[i - 1]);  // i - 1 对应物品 i
                }
            }
        }

        // 打印dp数组
        for(int[] arr : dp){
            System.out.println(Arrays.toString(arr));
        }
    }
}