算法训练营Day42(背包问题）

基础

非竞赛只需要搞懂0-1背包和完全背包

0-1背包基础

0-1背包是完全背包和多重背包的基础

n个物品，每个物品一个，每个物品有自己的重量和价值，，一个背包能装m物品，问最多装多少物品。

暴力解法，n个物品，2^n

dp数组：

可以二维，也可以优化成一维

二维

dp[i][j]:? 0-i的0物品任选一个放到背包j中，价值总和最大是多少。

递推公式

dp[i][j]

不放物品i，,物品是 i?背包为j，最大价值，

? ? ? ? dp[i-1][j]:不放物品i的最大价值。

放物品i: 物品为i-1{代表从0到i-1中选物品，所以物品i已经被放到背包}? ? ? ?? ?

????????dp[i-1]dp[j-weight[i]+value[i]?

????????{i-1代表0到i个物品，去掉i,?

?????????j-weight[i]{代表物品i放入背包，剩下的重量为这个}

? ? ? ? value[i]? ?：物品的价值

? ? ? ? dp[i-1][j-weight[i]]代表放入物品i，剩下物品的最大价值

? ? ? ? 两者相加就是当前背包的最大价值。

物品只有放与不放，所以递推公式:

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

初始化

dp[i][j]由上面{dp[i-1][j]}推除，或者左上角推出

还是初始化第一列和第一行

背包容量为0的时候，什么也不能放了，物品0到i都是初始化为0

第一行，这个要初始化的时候要看物品0的重量，如果为3

那么3 4这两个要初始化成value[0]

也就是weight[0]到i初始化成value[0]

遍历顺序

先遍历哪个都可以，因为从左上和上遍历，这两个都可以通过递推公式遍历完

代码

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);
    }

    /**
     * 动态规划获得结果
     * @param weight  物品的重量
     * @param value   物品的价值
     * @param bagSize 背包的容量
     */
    public static void testWeightBagProblem(int[] weight, int[] value, int bagSize){

        // 创建dp数组
        int goods = weight.length;  // 获取物品的数量
        int[][] dp = new int[goods][bagSize + 1];

        // 初始化dp数组
        // 创建数组后，其中默认的值就是0
        for (int j = weight[0]; j <= bagSize; j++) {
            dp[0][j] = value[0];
        }

        // 填充dp数组
        for (int i = 1; i < weight.length; i++) {
            for (int j = 1; j <= bagSize; j++) {
                if (j < weight[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]] + value[i]);
                }
            }
        }

        // 打印dp数组
        for (int i = 0; i < goods; i++) {
            for (int j = 0; j <= bagSize; j++) {
                System.out.print(dp[i][j] + "\t");
            }
            System.out.println("\n");
        }
    }
}

0-1背包-一维数组

压缩原理

因为每一层都是由上一层得到的，所以可以先拷贝到，通过滚动数组的形式实现原地修改！

dp数组含义

dp[j]? ? ? ?:? 容量为j时，背包最大价值为dp[j]

递推公式

不放物品i，因为这个数组是上一层拷贝下来的，上一层比如，物品1，那么这一层是物品2，直接拷贝下来，是不包含物品2的，

所以不妨物品i? ?：容量为j时，背包的最大价值就是dp[j]? {也就是抛去物品i的最大价值}

放物品i时：??

? ? ? ? 容量肯定要编程j-weight[j]的，现在放物品i，当前逻辑就要加上i的价值value[i]

? ? ? ? {{{其实从最开始，初始化，后面价值的总和都是加这个value[i]得到的

? ? ? ? 所以最大价值时dp[j-weight[i]]?

所以递推公式为：

? ? ? ? dp[j] = Math.max(dp[j],dp[j-weight]+value[i]){物理上就是数组当前位置和左面-weight位置}

初始化

容量为0 那么价值肯定0

所以初始化，dp[0]=0;

非0 的话，会被覆盖，默认为0就可

遍历顺序

现在数组是上一层的结果，想要倒叙遍历得到才是正常的计算

代码

 public static void main(String[] args) {
        int[] weight = {1, 3, 4};
        int[] value = {15, 20, 30};
        int bagWight = 4;
        testWeightBagProblem(weight, value, bagWight);
    }

    public static void testWeightBagProblem(int[] weight, int[] value, int bagWeight){
        int wLen = weight.length;
        //定义dp数组：dp[j]表示背包容量为j时，能获得的最大价值
        int[] dp = new int[bagWeight + 1];
        //遍历顺序：先遍历物品，再遍历背包容量
        for (int i = 0; i < wLen; i++){
            for (int j = bagWeight; j >= weight[i]; j--){
                dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
            }
        }
        //打印dp数组
        for (int j = 0; j <= bagWeight; j++){
            System.out.print(dp[j] + " ");
        }
    }

416. 分割等和子集

416. 分割等和子集 - 力扣（LeetCode）

class Solution {
    public boolean canPartition(int[] nums) {
        if(nums == null || nums.length == 0) return false;
        int sum = 0;
        for(int num : nums) {
            sum += num;
        }
   

        if(sum%2!=0) return false;
        int target = sum/2;
        //dp数组 ：含义：容量为j时，最大价值为dp[j]
        int [] dp = new int[target+1];
        //初始化
        //默认为0即可

        //遍历顺序
        //先遍历物品
        for(int i = 0;i<nums.length;i++){
            for(int j = target;j>=nums[i];j--){
                //递推公式
                dp[j] = Math.max(dp[j],dp[j-nums[i]]+nums[i]);
            }
        }
        return dp[target] == target;
    }
    
}