Berbagi teknologi

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

1. Masalah

Anda diberikan nomor array tidak kosong yang hanya berisi bilangan bulat positif. Tentukan apakah larik ini dapat dibagi menjadi dua himpunan bagian sehingga jumlah elemen kedua himpunan bagian tersebut sama.

2. Ide solusi 1

Solusi pemrograman dinamis

Masalah ini tidak dapat diselesaikan dengan menggunakan algoritma backtracking. Jika jumlah datanya besar, maka akan terjadi time out. Kita dapat menggunakan pemrograman dinamis.
Pertanyaan ini menentukan apakah jumlah elemen dari dua bagian sama jika array dibagi menjadi dua bagian. Pertama kita perlu menghitung jumlah semua elemen dalam array, dan kemudian menentukan apakah jumlah tersebut bilangan genap: jika bukan bilangan genap, berarti tidak dapat dibagi menjadi dua bagian yang sama persis, dan akan kembali salah secara langsung.
Kalau bilangan genap, kita tinggal menentukan apakah ada unsur yang jumlahnya sama dengan jumlah/2, maka sisanya juga harus sama dengan jumlah/2, artinya kita dapat membagi array menjadi dua bagian dengan elemen yang sama.
Maka permasalahannya sangat jelas saat ini, dengan asumsi sum/2 adalah kapasitas sebuah backpack, kita hanya perlu mencari beberapa elemen dan memasukkannya ke dalam backpack jika jumlah maksimum elemen yang ada di dalam backpack sama dengan jumlah /2, artinya kita dapat membagi array menjadi dua bagian yang sama besar. Bukankah ini masalah klasik ransel 0-1? Soal dasar knapsack pada rangkaian soal knapsack dapat dibaca dibawah ini untuk lebih jelasnya saya tidak akan mengulangi pendahuluan disini. Kita mencari rumus rekursinya dan mendefinisikan dp[i][j] untuk mewakili nilai maksimum yang diperoleh dengan memasukkan item ke-i ke dalam ransel berkapasitas j.
Nilai item ke-i adalah angka [i -1]:
Jika angka [i -1]>j berarti kapasitas ransel tidak mencukupi dan barang ke-i tidak bisa dimasukkan, sehingga kita tidak bisa memilih barang ke-i, maka
dp[i][j]=dp[i -1][j];
Kalau nums [i -1]<=j berarti barang ke-j bisa dimasukkan ke dalam backpack. Kita bisa memilih mau menaruhnya atau tidak, ambil saja nilai maksimalnya kapasitas ransel.Nilai maksimal ya
dp[i][j]=dp[i-1][j-bilangan[i-1]]+bilangan[i-1]
Jika kamu tidak melepaskannya
dp[i][j]=dp[i -1][j];
Ambil maksimal keduanya

Rumus dan kode rekursif terakhir adalah sebagai berikut:

#include <vector>
 
bool canPartition(std::vector<int>& nums) {
    // 计算数组中所有元素的和
    int sum = 0;
    for (int num : nums) {
        sum += num;
    }
    // 如果sum是奇数，说明数组不可能分成完全相等的两份
    if ((sum & 1) == 1) {
        return false;
    }
    // sum除以2
    int target = sum >> 1;
    int length = nums.size();
    std::vector<std::vector<int>> dp(length + 1, std::vector<int>(target + 1, 0));
    for (int i = 1; i <= length; ++i) {
        for (int j = 1; j <= target; ++j) {
            // 下面是递推公式
            if (j >= nums[i - 1]) {
                dp[i][j] = std::max(dp[i - 1][j], dp[i - 1][j - nums[i - 1]] + nums[i - 1]);
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    // 判断背包最大是否能存放和为target的元素
    return dp[length][target] == target;
}

Kita juga bisa menulis seperti ini. Array dua dimensi dp bertipe boolean. dp[i][j] menunjukkan apakah jumlah elemen i pertama dalam array dapat membentuk jumlah j. 0]=benar, artinya 0 elemen pertama (yaitu, tidak ada elemen) dapat membentuk jumlah 0.kode tampil seperti di bawah ini

#include <vector>
 
bool canPartition(std::vector<int>& nums) {
    // 计算数组中所有元素的和
    int sum = 0;
    for (int num : nums) {
        sum += num;
    }
    // 如果sum是奇数，说明数组不可能分成完全相等的两份
    if ((sum & 1) == 1) {
        return false;
    }
    // sum除以2得到target
    int target = sum >> 1;
    int length = nums.size();
    std::vector<std::vector<bool>> dp(length + 1, std::vector<bool>(target + 1, false));
    // base case
    dp[0][0] = true;
    for (int i = 1; i <= length; ++i) {
        for (int j = 0; j <= target; ++j) {
            // 递推公式
            if (j >= nums[i - 1]) {
                dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    // 返回能否找到和为target的子集
    return dp[length][target];
}

Kita melihat bahwa ketika menghitung array dua dimensi di atas, nilai saat ini hanya terkait dengan baris di atas, jadi kita dapat mengubahnya menjadi satu dimensi. Perhatikan bahwa loop for kedua harus flashback, jika tidak, nilai sebelumnya akan ditimpa dan hasilnya akan salah. , lihat lebih dekat
dp[j] = (dp[j] || dp[j - angka [i - 1]]);
Anda akan memahami bahwa nilai di akhir baris yang sama bergantung pada nilai sebelumnya. Jika ini bukan kilas balik, nilai sebelumnya akan diubah, yang akan menyebabkan kesalahan dalam penghitungan nilai berikutnya.Mari kita lihat kodenya

#include <vector>
 
bool canPartition(std::vector<int>& nums) {
    // 计算数组中所有元素的和
    int sum = 0;
    for (int num : nums) {
        sum += num;
    }
    // 如果sum是奇数，说明数组不可能分成完全相等的两份
    if ((sum & 1) == 1) {
        return false;
    }
    // sum除以2得到target
    int target = sum >> 1;
    int length = nums.size();
    std::vector<bool> dp(target + 1, false);
    // base case
    dp[0] = true;
    for (int i = 0; i < length; ++i) {
        // 注意这里j要倒序
        for (int j = target; j >= nums[i]; --j) {
            // 递推公式
            dp[j] = dp[j] || dp[j - nums[i]];
        }
    }
    // 返回能否找到和为target的子集
    return dp[target];
}

3. Ide solusi 2

Solusi algoritma DFS

Setiap elemen dapat dipilih atau tidak. Anda hanya perlu menentukan apakah jumlah elemen dalam semua kemungkinan kombinasinya sama dengan jumlah/2. Kita dapat menganggapnya sebagai pohon biner elemen saat ini, dan node anak di sebelah kanan mewakili pemilihan elemen saat ini. Node anak menunjukkan bahwa elemen saat ini tidak dipilih, seperti yang ditunjukkan pada gambar di bawah menunjukkan bahwa elemen saat ini tidak dipilih.

Mari kita lihat kode implementasi awal terlebih dahulu

#include <vector>
 
bool dfs(const std::vector<int>& nums, int target, int index) {
    // target等于0，说明存在一些元素的和等于sum/2，直接返回true
    if (target == 0) return true;
    // 如果数组元素都找完了，或者target小于0，直接返回false
    if (index == nums.size() || target < 0) return false;
    // 选择当前元素和不选择当前元素两种情况
    return dfs(nums, target - nums[index], index + 1) || dfs(nums, target, index + 1);
}
 
bool canPartition(std::vector<int>& nums) {
    // 计算数组中所有元素的和
    int sum = 0;
    for (int num : nums) sum += num;
    // 如果sum是奇数，说明数组不可能分成完全相等的两份
    if ((sum & 1) == 1) return false;
    // 调用dfs函数
    return dfs(nums, sum >> 1, 0);
}

Namun sayangnya karena jumlah perhitungannya yang terlalu besar akan menyebabkan waktu pengoperasiannya habis. Kita bisa mengoptimalkannya dan melihat kodenya.

#include <vector>
 
bool dfs(const std::vector<int>& nums, int index, int target, std::vector<std::vector<int>>& map) {
    // target等于0，说明存在一些元素的和等于sum/2，直接返回true
    if (target == 0) return true;
    // 如果数组元素都找完了，或者target小于0，直接返回false
    if (index >= nums.size() || target < 0) return false;
    // 如果此子问题已经被计算过，直接返回结果
    if (map[index][target] != -1) return map[index][target] == 1;
    // 选择当前元素
    bool select = dfs(nums, index + 1, target - nums[index], map);
    // 不选择当前元素
    bool unSelect = dfs(nums, index + 1, target, map);
    // 存储结果，并返回
    map[index][target] = select || unSelect ? 1 : 0;
    return select || unSelect;
}
 
bool canPartition(std::vector<int>& nums) {
    // 计算数组中所有元素的和
    int sum = 0;
    for (int num : nums) sum += num;
    // 如果sum是奇数，说明数组不可能分成完全相等的两份
    if (sum % 2 != 0) return false;
    // sum除以2
    int target = sum / 2;
    std::vector<std::vector<int>> map(nums.size(), std::vector<int>(target + 1, -1));
    return dfs(nums, 0, target, map);
}

4. Ide solusi 3

Solusi operasi bit

Operasi bit dapat digunakan di sini, tetapi kuncinya terletak pada beberapa batasan dalam pertanyaan, seperti array bilangan bulat positif yang tidak kosong, elemen dalam setiap array tidak akan melebihi 100, ukuran array tidak akan melebihi 200, dll. .
Prinsipnya sangat sederhana, kita hanya perlu menerapkan array bits[jumlah+1] dengan ukuran jumlah+1. Angka-angka dalam array hanya boleh 0 dan 1. Kita bisa membayangkannya sebagai bit biner yang sangat panjang, karena int dan Tipe panjangnya terlalu pendek, kami menggunakan array di sini. Kemudian setiap kali elemen dalam array dilintasi, seperti m, bit biner digeser ke kiri sebanyak m bit dan kemudian di-OR dengan bit biner asli. Terakhir, tentukan apakah bits[sum/2] bernilai 1, dan kembalikan nilai true jika bernilai 1.Deskripsi teksnya tidak terlalu jelas. Mari kita ambil Contoh 1 sebagai contoh untuk menggambar.

Terakhir, Anda akan menemukan aturannya, yaitu selama hasil akhir operasinya adalah 1, maka dapat digabungkan menggunakan elemen-elemen yang ada di dalam array. Pahami proses di atas, kodenya mudah untuk ditulis. Karena kita hanya perlu menentukan apakah nilai tengah pada bit biner tersebut adalah 1, kita hanya perlu menghitung bit rendahnya, dan bit tinggi tidak perlu dihitung sama sekali, karena dipindahkan ke kiri, dan bit tinggi bit tidak akan berdampak apa pun pada nilai tengah, jadi kita bisa melakukannya di sini. Sedikit optimasi, dan terakhir mari kita lihat kodenya.

#include <vector>
 
bool canPartition(std::vector<int>& nums) {
    // 计算数组中所有数字的和
    int sum = 0;
    for (int n : nums) {
        sum += n;
    }
    // 如果sum是奇数，直接返回false
    if ((sum & 1) == 1) {
        return false;
    }
    int len = sum / 2;
    // 这里bits的长度是len+1，因为我们只需要计算低位就行了，没必要计算所有的
    std::vector<char> bits(len + 1, 0);
    bits[0] = 1;
    for (int num : nums) {
        for (int j = len - num; j >= 0; j--) {
            bits[j + num] |= bits[j];
        }
        // 判断中位数如果是1，说明可以分成两种相等的子集，直接返回true，不需要再计算了
        if ((bits[len] & 1) != 0) {
            return true;
        }
    }
    return false;
}