【每日刷题】动态规划-代码随想录动规-11、12、13-Toy模板网

这篇具有很好参考价值的文章主要介绍了【每日刷题】动态规划-代码随想录动规-11、12、13。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1. 代码随想录-动规11.背包理论基础

问题背景：
有若干个物品对应各自的体积和价值，有一个容量确定的背包，有选择的将物品装进背包里，求可放进背包的最大价值。
思路：
定义dp数组：
dp[i][j]的含义：从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。
dp[i][j]递推公式：
不放物品i或放不下物品i：即背包容量为j，里面不放物品i的最大价值，此时dp[i][j]就是dp[i - 1][j]。(其实就是当物品i的重量大于背包j的重量时，物品i无法放进背包中，所以背包内的价值依然和前面相同。)
放物品i即放得下物品i：由dp[i - 1][j - weight[i]]推出，dp[i - 1][j - weight[i]] 为背包容量为j - weight[i]的时候不放物品i的最大价值，那么dp[i - 1][j - weight[i]] + value[i] （物品i的价值），就是背包放物品i得到的最大价值
所以递归公式： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
初始化：
dp[0][j]和dp[i][0]，dp[i][0]即背包容量为0，什么也放不下，所以dp[i][0]=0。
【每日刷题】动态规划-代码随想录动规-11、12、13,动态规划,算法,leetcode,java

代码：

import java.util.*;

/**
 * Created by wt on 2024/2/1.
 */
public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int M = sc.nextInt();
    int N = sc.nextInt();
    int[] weights = new int[M];
    for (int i = 0; i < M; i++) {
      weights[i] = sc.nextInt();
    }
    int[] values = new int[M];
    for (int i = 0; i < M; i++) {
      values[i] = sc.nextInt();
    }
    
    int[][] dp = new int[M][N+1];
    for (int temp=weights[0]; temp<N+1; temp++){
        dp[0][temp] = values[0];
    }
    
    for (int i=1; i<M; i++){
        for (int j=1; j<N+1; j++){
            if (weights[i] > j){
                dp[i][j] = dp[i-1][j];
            }
            else{
                dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-weights[i]]+values[i]);
            }
        }
    }
    System.out.println(dp[M-1][N]);


    sc.close();
  }
}

注意：

数组大小为N+1，而不是N。因为把包容量为0也算上了。
max函数应为Math.max()
dp数组初始化dp[0][j]只有当包容量大于等于物品0的体积时，dp才等于物品0的价值。

2.代码随想录-动规12.背包理论基础2

数组降维
相当于第i层覆盖第i-1层
dp数组初始化：初始化数值不覆盖原始数值即可。若都为正数，则初始化为0；若有负数，则初始化为负无穷。
递推公式：dp[j] = max(dp[j], dp[j-weight[i]]+value[i])
遍历顺序：不能颠倒，先遍历i，物品，再遍历容量j。容量j从后往前遍历。

import java.util.*;

/**
 * Created by wt on 2024/2/1.
 */
public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int M = sc.nextInt();
    int N = sc.nextInt();
    int[] weights = new int[M];
    for (int i = 0; i < M; i++) {
      weights[i] = sc.nextInt();
    }
    int[] values = new int[M];
    for (int i = 0; i < M; i++) {
      values[i] = sc.nextInt();
    }
    
    //从这里开始不同
    int[]dp = new int[N+1];
    
    for (int i=0; i<M; i++){
        for (int j=N; j>=weights[i]; j--){
                dp[j] = Math.max(dp[j], dp[j-weights[i]]+values[i]);
        }
    }
    System.out.println(dp[N]);


    sc.close();
  }
}

3.代码随想录-动规13.LC416分割等和子集

题目链接
套用背包解法：如果能找到==sum/2的组合，则证明可以分割成相等子集。若sum是奇数，因为所有数字为整数，则直接返回false。
因为一个数字只能用一次，所以是01背包
01背包的递推公式为：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); dp[j]为容量为j的背包的最大价值

套用后：
背包容量即为target和，物品价值为数值nums[i]，物品重量也为nums[i]
含义：dp[j]为容量为j的背包的最大数值和
公式：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
初始化：因为所有数字都为正数，初始化为0不覆盖就可以。
最后检验，当dp[target] == target时，返回true。

注意：背包易错：
定义dp数组时，int[] dp = new int[?]，这里数组长度为背包容量+ 1

代码：文章来源地址https://www.toymoban.com/news/detail-836463.html

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int temp=0; temp<nums.length; temp++){
            sum += nums[temp];
        }
        if (sum%2 != 0){
            return false;
        }
        int target = sum/2;
        int[] dp = new int[target+1];
        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]);
            }
        }
        if (target == dp[target]){
            return true;
        }
        return false;
    }
}