LeetCode DayDynamic Programming Bahagian 3

Masalah Beg 0-1

Penerangan topik

Ming ialah seorang saintis yang perlu menghadiri persidangan saintifik antarabangsa yang penting untuk membentangkan penyelidikan terbarunya. Dia perlu membawa beberapa bahan penyelidikan bersamanya, tetapi dia mempunyai ruang terhad dalam beg pakaiannya. Bahan penyelidikan ini termasuk peralatan eksperimen, kesusasteraan, sampel eksperimen, dsb., yang setiap satunya menempati ruang yang berbeza dan mempunyai nilai yang berbeza.

Ruang bagasi Ming ialah N. Tanya Ming bagaimana dia harus memilih untuk membawa bahan penyelidikan dengan nilai paling tinggi. Setiap bahan kajian hanya boleh dipilih sekali, dan hanya ada dua pilihan: pilih atau jangan pilih, dan tiada pemotongan boleh dilakukan.

Input Penerangan
Baris pertama mengandungi dua integer positif, integer pertama M mewakili jenis bahan penyelidikan, dan integer positif kedua N mewakili ruang bagasi Ming.

Barisan kedua mengandungi integer positif M yang mewakili ruang yang diduduki oleh setiap jenis bahan penyelidikan.

Baris ketiga mengandungi integer positif M yang mewakili nilai setiap bahan penyelidikan.

Keterangan Output
Keluarkan integer yang mewakili nilai maksimum bahan penyelidikan yang boleh dibawa oleh Ming.

Contoh Input
6 1
2 2 3 1 5 2
2 3 1 5 4 3

Contoh output
5

Petunjuk
Ming mampu membawa 6 bahan kajian, tetapi ruang bagasi hanya 1, dan bahan kajian yang menduduki 1 ruang bernilai 5, jadi jawapan akhir ialah output 5.

Julat data:
1 <= N <= 5000
1 <= M <= 5000
Ruang yang diduduki oleh bahan penyelidikan dan nilai bahan penyelidikan kedua-duanya kurang daripada atau sama dengan 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]);
    }
}




</p>
<p>1, tatasusunan dp bermakna kita boleh memperoleh nilai maksimum untuk item i dan saiz beg sasaran j. Baris menunjukkan item dan lajur mewakili saiz beg.</p>

<p>2, untuk init, kita init baris pertama dan kol pertama( tetapi sebenarnya kita init kol secara lalai 0, itu bermakna )</p>

<p>3, hubungan regresi ialah: untuk setiap item:<br>
    a, jika berat item lebih berat daripada saiz beg, kami tidak boleh memilih item dan saiz semasa adalah saiz koleksi item yang dipilih sebelum ini. <br>
    b, jika berat barang ok, kita kena bandingkan saiz koleksi barang yang dipilih sebelum ini tolak saiz barang semasa (kalau kita tidak buat, jumlah saiz akan menjadi saiz + saiz daripada item semasa, ia akan memecahkan logik tatasusunan dp kami).</p>

<p>Di sini, ialah susunan gelung berganda, kerana kita boleh menggunakan tatasusunan 2-D untuk merekod semua hasil dan mencari baris semasa daripada baris sebelumnya.</p>
<h2>
  
  
  Selain itu, kita boleh menggunakan tatasusunan 1-D untuk merealisasikannya.
</h2>



<pre class="brush:php;toolbar:false">    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]);
            }

tukar kepada

        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. Pembahagian Jumlah Subset Sama

Memandangkan nombor tatasusunan integer, kembalikan benar jika anda boleh membahagikan tatasusunan kepada dua subset supaya jumlah elemen dalam kedua-dua subset adalah sama atau palsu sebaliknya.

Contoh 1:

Input: nombor = [1,5,11,5]
Output: benar
Penjelasan: Tatasusunan boleh dibahagikan sebagai [1, 5, 5] dan [11].
Contoh 2:

Input: nums = [1,2,3,5]
Output: palsu
Penjelasan: Tatasusunan tidak boleh dibahagikan kepada subset jumlah yang sama.

Kekangan:

1 <= nums.length <= 200
1 <= angka[i] <= 100
Halaman Asal

    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 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;  
    }





          

            
        
Atas ialah kandungan terperinci LeetCode DayDynamic Programming Bahagian 3. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!