LeetCode Day動的プログラミング パート 3

0-1 バッグ問題

トピックの説明

ミンは科学者で、最新の研究を発表するために重要な国際科学会議に出席する必要があります。彼はいくつかの研究資料を持っていく必要がありますが、スーツケースのスペースが限られています。これらの研究資料には、実験装置、文献、実験サンプルなどが含まれ、それぞれが異なる空間を占め、異なる価値を持ちます。

ミンの荷物スペースは N です。最も価値のある研究資料を運ぶにはどのように選択すればよいかをミンに尋ねます。各研究材料は 1 回だけ選択でき、選択は選択するか選択しないの 2 つだけであり、カットはできません。

入力の説明
最初の行には 2 つの正の整数が含まれており、最初の整数 M は研究資料の種類を表し、2 番目の正の整数 N はミンの荷物スペースを表します。

2 行目には、各種類の研究資料が占めるスペースを表す M 個の正の整数が含まれています。

3 行目には、各研究資料の価値を表す M 個の正の整数が含まれます。

出力の説明
明が所持で​​きる研究資材の最大値を表す整数を出力します。

入力例
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配列は、アイテムiとターゲットバッグサイズjの最大値を取得できることを意味します。行はアイテムを示し、列はバッグのサイズを表します。

2、init の場合、1 行目と 1 列目を初期化します (ただし、実際にはデフォルトで列を初期化します 0、つまり )

3、回帰関係は次のとおりです: 各アイテムについて:
a、アイテムの重量がバッグのサイズより重い場合、アイテムを選択することはできず、現在のサイズは以前に選択したアイテムのコレクションのサイズになります。
b、アイテムの重量に問題がない場合は、以前に選択したアイテムのコレクションのサイズから現在のアイテムのサイズを引いたものを比較する必要があります (これを行わない場合、合計サイズはサイズ + サイズになります)現在のアイテムを削除すると、dp 配列のロジックが壊れます)。

ここでは、2 次元配列を使用してすべての結果を記録し、前の行から現在の行を検索できるため、二重ループの順序を示します。

また、1 次元配列を使用してそれを実現することもできます。

    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 を指定すると、両方のサブセットの要素の合計が等しくなるように配列を 2 つのサブセットに分割できる場合は true を返し、それ以外の場合は false を返します。

例 1:

入力: nums = [1,5,11,5]
出力: true
説明: 配列は [1, 5, 5] および [11] としてパーティション化できます。
例 2:

入力: nums = [1,2,3,5]
出力: false
説明: 配列を等しい和のサブセットに分割することはできません。

制約:

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 中国語 Web サイトの他の関連記事を参照してください。