LeetCode Day动态编程第 3 部分

0-1 袋子问题

主题描述

明是一位科学家，他需要参加一个重要的国际科学会议来展示他的最新研究成果。他需要带一些研究资料，但他的行李箱空间有限。这些研究资料包括实验设备、文献、实验样本等，各自占据不同的空间，具有不同的价值。

Ming的行李空间为N，请问Ming应该如何选择携带最有价值的研究资料。每个研究材料只能选择一次，并且只有选择或不选择两种选择，并且不能进行剪切。

输入说明
第一行包含两个正整数，第一个整数M代表研究材料的类型，第二个正整数N代表Ming的行李空间。

第二行包含 M 个正整数，代表每种研究材料占用的空间。

第三行包含M个正整数，代表每个研究材料的价值。

输出描述
输出一个整数，代表Ming可以携带的研究材料的最大值。

输入示例
6 1
2 2 3 1 5 2
2 3 1 5 4 3

输出示例
5

提示
小明可以携带6个研究材料，但行李空间只有1个，而占用1个空间的研究材料价值5个，所以最终答案是输出5。

数据范围：
1 1 研究资料占用空间和研究资料价值均小于等于1000。

public class Main{
    public static void main (String[] args) {
    /* code */
    Scanner s = new Scanner(System.in);

        int M = s.nextInt();
        int N = s.nextInt();
        // clear buffer symbol /n
        s.nextLine();

    String w = s.nextLine();
    String v = s.nextLine();

    int[] weight = Arrays.stream(w.split(" "))
                        .mapToInt(Integer::valueOf)
                        .toArray();
    int[] value = Arrays.stream(v.split(" "))
                        .mapToInt(Integer::valueOf)
                        .toArray();

    int[][] dp = new int[M][N+1];


    for(int i=weight[0]; i<=N; i++){
        dp[0][i] = value[0];
    }

    for(int i=1; i<M; i++){
        for(int j=1; j<=N; j++){
            if(weight[i] > j){
                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]);
    }
}

1，dp数组意味着我们可以获得item i和目标bag size j的最大值。行表示物品，列表示包的尺寸。

2，对于init，我们初始化第一行和第一列（但实际上我们默认初始化列为0，这意味着）

3，回归关系为：对于每一项：
a、如果物品的重量大于包的尺寸，则无法选择该物品，当前尺寸为之前选择的物品集合的尺寸。
b、如果物品的重量可以，我们必须比较之前选择的物品的集合的大小减去当前物品的大小（如果我们不这样做，则总大小将是大小 + 大小当前项目的，它将破坏我们的 dp 数组的逻辑）。

这里，是双循环的顺序，因为我们可以用一个二维数组来记录所有结果，并从上一行中查找当前行。

另外，我们可以使用一维数组来实现。

    for(int i=1; i<M; i++){
        for(int j=1; j<=N; j++){
            if(weight[i] > j){
                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]);
            }

更改为

        int[] dp = new int[target+1];

        for(int i=1; i<nums.length; i++){
            for(int j=target; j>=1; j--){
                if(nums[i] > j){
                    continue;
                }
                dp[j] = Math.max(dp[j], dp[j-nums[i]] + nums[i]);    
            }
        }

---

416. 划分子集和相等

给定一个整数数组 nums，如果可以将数组划分为两个子集，使得两个子集中的元素之和相等，则返回 true，否则返回 false。

示例1：

输入：nums = [1,5,11,5]
输出：true
说明：数组可以分为 [1, 5, 5] 和 [11]。
示例2：

输入：nums = [1,2,3,5]
输出：假
解释：数组不能划分为等和子集。

限制：

1 1 原始页面

    public boolean canPartition(int[] nums) {
        int sum = Arrays.stream(nums).sum();
        if(sum%2==1){
            return false;
        }
        int target = sum>>1;
        int[][] dp = new int[nums.length][target+1];

        for(int i=nums[0]; i<=target; i++){
            dp[0][i] = nums[0];
        }

        for(int i=1; i<nums.length; i++){
            for(int j=1; j<=target; j++){
                if(nums[i] > j){
                    dp[i][j] = dp[i-1][j];
                }else{
                    dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-nums[i]] + nums[i]);
                }     
            }
        }

        return dp[nums.length-1][target] == target;  
    }

以上是LeetCode Day动态编程第 3 部分的详细内容。更多信息请关注PHP中文网其他相关文章！