代码随想录算法训练营第三十五天| 46. 携带研究材料 46. 携带研究材料（滚动数组）416. 分割等和子集

入营第三十五天
难度：

• 计划任务
• 完成任务

46. 携带研究材料

动态规划五部曲：
1.确定dp数组以及下标含义 dp[i][j]表示背包容量为j时，从[0-i]中进行物品选择，价值总和最大是多少
2.确定递推公式 两种情况，①不放第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])
3.递推数组初始化 背包容量为0的时候 所有物品都放不进去，数组设置为0，以及对于仅放第一件物品的情况，当背包容量大于等于第一个物品的体积时>=weight[0]，dp数组要摄者为value[0]
4.确定遍历顺序 先遍历物品再遍历容量
5.举例推导递推公式

import java.util.Scanner;
public class Main{
    public static void main(String[] agrs){
        Scanner scanner = new Scanner(System.in);
        //m代表研究材料的种类
        int m = scanner.nextInt();
        //n代表行李空间
        int n = scanner.nextInt();

        int[] weight = new int[m];
        int[] value = new int[m];

        for(int i=0;i<m;i++){
            weight[i] = scanner.nextInt();
        }
        for(int i=0;i<m;i++){
            value[i] = scanner.nextInt();
        }

        int[][] dp = new int[m][n+1];
        //第一列置为0(行李空间为0时所有物品都放不进)
        for(int i=0;i<m;i++){
            dp[i][0] = 0;
        }
        //
        for(int i=weight[0];i<=n;i++){
            dp[0][i]=value[0];
        }

        for(int i=1;i<m;i++){
            for(int j=0;j<=n;j++){
                if(j<weight[i]){
                    dp[i][j] = dp[i-1][j];
                }else{
                    dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i]);   
                }
            }
        }
        System.out.println(dp[m-1][n]);
    }
}

46. 携带研究材料（滚动数组）

动态规划五部曲：
1.确定dp数组以及下标含义 dp[j]代表容量为j的背包，所背的物品最大价值是多少
2.确定递推公式 dp[j] = Math.max(dp[j],dp[j-weight[i]]+value[i])
3.递推数组初始化 dp[0] = 0
4.确定遍历顺序 物品正序遍历，容量逆序遍历
5.举例推导递推公式

import java.util.Scanner;
public class Main{
    public static void main(String[] agrs){
        Scanner scanner = new Scanner(System.in);
        //物品种类
        int m = scanner.nextInt();
        //行李空间
        int n = scanner.nextInt();

        int[] weight = new int[m];
        int[] value = new int[m];

        for(int i=0;i<m;i++){
            weight[i] = scanner.nextInt();
        }
        for(int i=0;i<m;i++){
            value[i] = scanner.nextInt();
        }

        int[] dp = new int[n+1];
        dp[0] = 0;
        for(int i = 0;i < m;i++){
            for(int j = n;j>=weight[i];j--){
                dp[j] = Math.max(dp[j],dp[j-weight[i]]+value[i]);
            }
        }
        System.out.print(dp[n]);
    }
}

416. 分割等和子集

动态规划五部曲：
1.确定dp数组以及下标含义
2.确定递推公式
3.递推数组初始化
4.确定遍历顺序
5.举例推导递推公式

class Solution {
    public boolean canPartition(int[] nums) {
        if(nums.length==0){
            return false;
        }
        int len = nums.length;
        int sum=0;
        for(int i=0;i<len;i++){
            sum+=nums[i];
        }
        if(sum%2!=0){
            return false;
        }
        int target = sum/2;
        int[] dp = new int[target+1];
        for(int i=0;i<len;i++){
            for(int j=target;j>=nums[i];j--){
                dp[j] = Math.max(dp[j],dp[j-nums[i]]+nums[i]);
                if(dp[j] == target){
                    return true;
                }
            }
        }
        return dp[target] == target;
    }
}