Berbagi teknologi

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

satu,Array dua dimensi

1、persamaan transisi keadaan：

• Jangan letakkan itemi : Dikurangi dari dp[i - 1][j], yaitu kapasitas ransel adalah j dan nilai maksimum item i tidak ditempatkan di dalamnya, dp[i][j] adalah dp[i - 1] [j]. (Bahkan bila berat barang i lebih besar dari berat ransel j, maka barang i tidak bisa dimasukkan ke dalam ransel, sehingga nilai di dalam ransel masih sama seperti sebelumnya.)
• Masukkan item i: Dikurangi dari dp[i - 1][j - berat[i]], dp[i - 1][j - berat[i]] adalah kapasitas maksimum ransel tanpa barang i bila kapasitasnya j - berat[ i] bernilai, maka dp[i - 1][j - berat[i]] + value[i] (nilai item i) adalah nilai maksimum yang diperoleh dengan memasukkan item i ke dalam ransel

Jadi rumus rekursifnya: dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - Weight[i]] + value[i]);

2. Inisialisasi

(1) Berdasarkan definisi dp[i][j], jika kapasitas ransel j adalah 0, yaitu dp[i][0], barang apa pun yang dipilih, nilai total ransel harus sama 0.

(2) Nyatakan persamaan transisi dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - bobot[i]] + value[i]); terlihat i berasal dari i-1, sehingga harus diinisialisasi ketika i bernilai 0.

dp[0][j], yaitu: i adalah 0, ketika menyimpan item nomor 0, nilai maksimum yang dapat disimpan oleh ransel dengan kapasitas masing-masing.

Maka jelas jika j < berat[0], dp[0][j] seharusnya 0, karena kapasitas ransel lebih kecil dari berat barang bernomor 0.

Jika j >= berat[0], dp[0][j] seharusnya bernilai[0], karena kapasitas ransel cukup untuk menampung item nomor 0.

for (int j = 0 ; j < weight[0]; j++) {
    dp[0][j] = 0;
}
// 正序遍历
for (int j = weight[0]; j <= bagweight; j++) {
    dp[0][j] = value[0];
}

(3) Inisialisasi subskrip lainnya:

dp[i][j] = maks(dp[i - 1][j], dp[i - 1][j - bobot[i]] + nilai[i])

dp[1][1] = max(dp[0][1], dp[0][1- berat[i]] + nilai[i]) harus di sebelah kiri dan di atasnya,

Oleh karena itu, ini harus sudah diinisialisasi dan dapat diatur ke nilai apa pun. Untuk kenyamanan, ini diinisialisasi ke 0 secara default.

2. Satu dimensi (array bergulir)

1. Pada larik dp satu dimensi, dp[j] artinya: tas ransel berkapasitas j dapat membawa barang dengan nilai maksimal dp[j]

dp[j] = max(dp[j], dp[j - weight[i]] + value[i])

2. Inisialisasi

(1) dp[0]=0, karena nilai maksimal barang yang dibawa oleh tas ransel berkapasitas 0 adalah 0.

(2) Asumsikan nilai item lebih besar dari 0,Agar tidak tertimpa dengan nilai awal, jadi dpInisialisasi arrayKapan , semuanya awalnya 0

3. Urutan lintasan

Lintasi dalam urutan terbalik

Penjelasan 1: Nilai di akhir daftar perlu ditentukan dengan membandingkannya dengan nilai sebelumnya yang diperoleh dengan menelusuri level sebelumnya.

Penjelasan 2: Hanya terdapat satu tas ransel 01 untuk setiap tas ransel, Ditaruh atau tidaknya tas ini berkaitan dengan status tas sebelumnya, Array di sebelah kiri adalah kuantitas yang menjelaskan status tas sebelumnya, dan nomornya di sebelah kanan adalah status pending dari tas saat ini. Dalam kode tersebut, nomor di sebelah kiri diperlukan untuk menentukan array di sebelah kanan, sehingga nomor di sebelah kiri tidak dapat dimusnahkan sebelum nomor di sebelah kanan dihitung.

Penjelasan 3 : Untuk dua dimensi, hasil setiap angka dp baru yang saya punya berasal dari atas dan kiri, sebenarnya harusnya seperti ini dalam satu dimensi, tetapi dalam satu dimensi, jika masih dari kiri ke kanan, maka kiri saya yang sebenarnya Angka-angka telah diperbarui ( Sisi kiri bukan lagi sisi kiri “asli”!Hal ini akan menyebabkan penghitungan ganda ), meskipun puncaknya masih merupakan puncak asli, angka yang diperoleh salah.Dan jika kita melintasi dari kanan ke kiri pada layer backpack (lapisan dalam), maka elemen di sebelah kiri akan selaluItu tidak akan ditimpa dengan nilai baru karena operasi saya sebelumnya., sehingga dapat diperoleh nilai yang benar.

3. Aplikasi

1. Diberikan array tak kosong yang hanya berisi bilangan bulat positif. Apakah mungkin untuk membagi array ini menjadi dua himpunan bagian sehingga jumlah elemen dari kedua himpunan bagian tersebut sama?

Catatan: Elemen dalam setiap array tidak akan melebihi 100 dan ukuran array tidak akan melebihi 200

Contoh 1:

• Masukan: [1, 5, 11, 5]
• Keluaran: benar
• Penjelasan: Array dapat dibagi menjadi [1, 5, 5] dan [11]

menganalisa:

Barangnya adalah aku,

Beratnya adalah angka[i], nilainya juga angka[i], dan volume ranselnya adalah jumlah/2.

Mirip dengan ransel 01

Persamaan transisi keadaan:

dp[j] = max(dp[j], dp[j - nums[i]] + nums[i])

// 开始 01背包
for(int i = 0; i < nums.size(); i++) {
    for(int j = target; j >= nums[i]; j--) {
        dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
    }
}
// 集合中的元素正好可以凑成总和target
if (dp[target] == target) return true;

2. Terdapat tumpukan batu, dan berat setiap batu merupakan bilangan bulat positif.

Setiap putaran, pilih dua batu mana saja dan hancurkan bersama-sama. Misalkan berat batu masing-masing adalah x dan y, dan x <= y. Maka kemungkinan hasil penghancurannya adalah sebagai berikut :

Jika x == y, maka kedua batu tersebut akan hancur sempurna;

Jika x != y, maka batu bermassa x akan pecah seluruhnya, dan batu berbobot y akan mendapat massa baru sebesar yx.

Pada akhirnya, paling banyak hanya tersisa satu batu. Mengembalikan bobot sekecil mungkin dari batu ini. Jika tidak ada batu yang tersisa, kembalikan 0.

Contoh:

• Masukan: [2,7,4,1,8,1]
• Keluaran: 1

menganalisa:

Usahakan untuk membagi batu menjadi dua tumpukan dengan berat yang sama, sehingga batu terkecil yang tersisa setelah tumbukan

Kemudian bagilah menjadi dua tumpukan batu. Berat total satu tumpukan batu adalah dp[target], dan berat total tumpukan lainnya adalah jumlah - dp[target].

Saat menghitung target, target = jumlah / 2 karena dibulatkan ke bawah, jadi jumlah - dp[target] harus lebih besar atau sama dengan dp[target]

Maka berat minimum batu yang tersisa setelah tumbukan adalah (jumlah - dp[target]) - dp[target]

for (int i = 0; i < stones.length; i++) {
//采用倒序
    for (int j = target; j >= stones[i]; j--) {
        dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);
    }
}
//结果
sum - 2 * dp[target];

dikutip dari:Catatan Kode Acak