【动态规划】背包问题汇总

0-1背包问题

题目描述

给一个可装载重量为W的背包和N个物品，每个物品有重量和价值两个属性，其中第i个物品的重量wt[i],
价值为val[i],问此背包装物品，能装的最大价值是多少
例：N=3,W=4
wt=[2,1,3]
val=[4,2,3]

算法思想

定义dp数组dp[i][j] ：对于前i个物品，当前背包容量为j,这种情况下背包可以装的最大价值为dp[i][j]

代码实现

public class package01 {


    public static int bag01(int N,int W,int[] wt,int[] val){
        int[][] dp=new int[N+1][W+1];
        for (int p = 0; p <= N ; p++) {   dp[...][0]=0 当背包容量为0时，此时最大价值为0
            dp[p][0]=0;
        }
        for (int k = 0; k <= W ; k++) {   dp[0][...]=0 当物品个数为0时，此时最大价值为0
            dp[0][k]=0;
        }

        for (int i = 1; i <=N ; i++) {
            for (int j = 1; j <= W; j++) {
                if(j < wt[i-1]){  如果当前背包容量小于要放入的物品i的重量(对应wt数组下标为i-1)
                    dp[i][j]=dp[i-1][j]; 不放入，用子状态更新，此时子状态为前i-1个物品，背包容量还为j，因为物品i没放入
                }else{ 					物品i能放下，比较是不放的价值大，还是放下的价值大？
                    dp[i][j]=Math.max(dp[i-1][j],   不放的价值
                                      dp[i-1][j-wt[i-1]]+val[i-1]);  放入i的价值，此时子状态为i-1个物品，背包容量为j-放入的i物品的重量  +物品i的价值
                }
            }
        }

        return dp[N][W];
    }

    public static void main(String[] args) {
        int N=3,W=4;
        int[] wt= new int[]{2,1,3};
        int[] val= new int[]{4,2,3};

        int MaxValue = package01.bag01(N, W, wt, val);
        System.out.println(MaxValue);        ====>6
    }

子集背包问题

剑指 Offer II 101. 分割等和子集 leetcode 416

题目描述

给定一个非空的正整数数组 nums ，请判断能否将这些数字分成元素和相等的两部分。

输入：nums = [1,2,3,5]
输出：false
解释：nums 不可以分为和相等的两部分

算法思想

把该问题转换为背包问题，nums数组里的数为物品，要凑成的子集为背包容量

代码实现

class Solution {
    public boolean canPartition(int[] nums) {
        int sum=0;
        for(int num:nums){       加和
            sum+=num;
        }
        if(sum%2!=0){    如果不能平分为两个大小相同的子集，返回false
            return false;
        }
        boolean [][] dp = new boolean[nums.length+1][sum/2+1];
        for(int i=0;i<=nums.length;i++){    dp[...][0] 可以凑出来当前子集大小为0的情况，返回true
            dp[i][0]=true;
        }
        for(int i=1;i<=sum/2;i++){         dp[0][...] 前0个元素凑不出任何子集的大小，返回false
            dp[0][i]=false;
        }
        for(int i =1;i<=nums.length;i++){
            for(int j =1;j<=sum/2;j++){
                if(j<nums[i-1]){  不放入
                    dp[i][j]=dp[i-1][j];  
                }else{         不放入或放入，看看哪种情况能恰好凑满子集(背包)
                    dp[i][j]=dp[i-1][j] || dp[i-1][j-nums[i-1]];  
                }

            }
        }
        return dp[nums.length][sum/2];

    }
}

完全背包问题

题目描述

给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。

假设每一种面额的硬币有无限个。

题目数据保证结果符合 32 位带符号整数。

输入：amount = 5, coins = [1, 2, 5]
输出：4
解释：有四种方式可以凑成总金额：
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

输入：amount = 3, coins = [2]
输出：0
解释：只用面额 2 的硬币不能凑成总金额 3 。

输入：amount = 10, coins = [10]
输出：1

算法思想

完全背包问题与之前背包的不同就是 物品的数量可以重复
本题是求能凑出给定面额的组合数

https:///a523900582/article/details/121357426?spm=1001.2014.3001.5502
是求能凑出给定面额的最少硬币数

代码实现

class Solution {
    public int change(int amount, int[] coins) {

        
        int [][] dp = new int[coins.length+1][amount+1];
        	#basecase
        for(int i=0;i<=coins.length;i++){  凑出0块钱 1种方法，那就是没有
            dp[i][0]=1;    
        }
        for(int i=1;i<=amount;i++){        前0个硬币凑不出任何面值的钱
            dp[0][i]=0;
        }
        for(int i =1;i<=coins.length;i++){
            for(int j =1;j<=amount;j++){
                if(j<coins[i-1]){ 
                    dp[i][j]=dp[i-1][j];  
                }else{       此时为dp[**i**][j-coins[i-1]]因为硬币可重复
                    dp[i][j]=dp[i-1][j] + dp[i][j-coins[i-1]];   
                }
            }
        }
        return dp[coins.length][amount];


    }
}