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

2024-01-10 14:35:08

基础

非竞赛只需要搞懂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;
    }
    
}

文章来源:https://blog.csdn.net/weixin_65728526/article/details/135489418
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。