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中文網其他相關文章！