Teknologian jakaminen

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

1. Ongelma

Sinulle annetaan ei-tyhjä taulukon numerot, jotka sisältävät vain positiivisia kokonaislukuja. Määritä, voidaanko tämä taulukko jakaa kahteen osajoukkoon niin, että näiden kahden osajoukon elementtien summa on yhtä suuri.

2. Ratkaisuidea 1

Dynaaminen ohjelmointiratkaisu

Tätä ongelmaa ei voida ratkaista takaisinseuranta-algoritmilla. Jos tietomäärä on suuri, se aikakatkaistaan. Voimme käyttää dynaamista ohjelmointia.
Tämä kysymys määrittää, onko kahden osan elementtien summa yhtä suuri, jos taulukko jaetaan kahteen osaan. Ensin meidän on laskettava taulukon kaikkien elementtien summa ja määritettävä sitten, onko summa parillinen luku: jos se ei ole parillinen luku, se tarkoittaa, että sitä ei voida jakaa kahteen täysin yhtä suureen osaan, ja se palauttaa vääriä suoraan.
Jos se on parillinen luku, meidän on vain määritettävä, onko olemassa joitakin alkioita, joiden summa on yhtä suuri kuin summa/2, niin lopunkin on oltava yhtä suuri kuin summa/2, mikä tarkoittaa sitä voimme jakaa taulukon kahteen osaan, joissa on yhtä suuret elementit.
Silloin ongelma on tällä hetkellä hyvin selvä. Olettaen, että summa/2 on reppun kapasiteetti, meidän tarvitsee vain löytää joitakin elementtejä ja laittaa ne reppuun /2, se tarkoittaa, että voimme laittaa taulukon Jaa kahteen yhtä suureen osaan. Eikö tämä ole klassinen 0-1-reppuongelma? Reppuongelmien sarjan perusreppuongelma on luettavissa alta lisätietoja varten. En toista esittelyä tässä. Etsimme hänen rekursiokaavaa ja määrittelemme dp[i][j] edustamaan maksimiarvoa, joka saadaan laittamalla i:s esine reppuun, jonka kapasiteetti on j.
I:nnen kohteen arvo on numerot [i -1]:
Jos numerot [i -1]>j, se tarkoittaa, että repun kapasiteetti ei riitä ja i:ttä tuotetta ei voida laittaa, joten emme voi valita i:ttä tuotetta,
dp[i][j]=dp[i -1][j]；
Jos numerot [i -1]<=j, se tarkoittaa, että j:nnen tuotteen voi laittaa reppuun repun kapasiteetti Suurin arvo kyllä
dp[i][j]=dp[i-1][j-numerot[i-1]]+numerot[i-1]
Jos et päästä irti
dp[i][j]=dp[i -1][j]；
Ota kahdesta maksimi

Lopullinen rekursiivinen kaava ja koodi ovat seuraavat:

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

Voimme kirjoittaa myös näin. Kaksiulotteinen taulukko dp on loogista tyyppiä, joka osoittaa, voiko taulukon ensimmäisten i-elementtien summa muodostaa summan dp[0][. 0]=true, mikä tarkoittaa, että ensimmäiset 0 elementtiä (eli ei elementtejä) voivat muodostaa summan 0.koodi näytetään alla

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

Näemme, että laskettaessa yllä olevaa kaksiulotteista taulukkoa nykyinen arvo liittyy vain yllä olevaan riviin, joten voimme muuttaa sen yksiulotteiseksi. Huomaa, että toisen for-silmukan on oltava flashback, muuten edellinen arvo kirjoitetaan päälle ja tulos on väärä, katso tarkemmin
dp[j] = (dp[j] || dp[j - määrät [i - 1]]);
Ymmärrät, että saman rivin lopussa oleva arvo riippuu edellisestä. Jos se ei ole takauma, aiempaa arvoa muutetaan, mikä aiheuttaa virheen myöhemmän arvon laskennassa.Katsotaanpa koodia

#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. Ratkaisuidea 2

DFS-algoritmiratkaisu

Jokainen elementti voidaan valita tai ei. Sinun tarvitsee vain määrittää, onko elementtien summa kaikissa mahdollisissa yhdistelmissä yhtä suuri kuin summa/2. Vasen lapsisolmu edustaa valintaa nykyinen elementti ja oikea alisolmu edustaa nykyisen elementin valintaa, kuten alla olevassa kuvassa näkyy. Oranssi solmu osoittaa, että nykyinen elementti on valittuna osoittaa, että nykyistä elementtiä ei ole valittu.

Katsotaanpa ensin alustavaa käyttöönottokoodia

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

Mutta valitettavasti, koska laskentamäärä on liian suuri, se aiheuttaa toiminnan aikakatkaisun. Voimme optimoida sen ja katsoa koodia.

#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. Ratkaisuidea 3

Bittikäyttöinen ratkaisu

Tässä voidaan käyttää bittioperaatioita, mutta avain piilee tietyissä kysymyksen rajoituksissa, kuten ei-tyhjä positiivisten kokonaislukujen matriisi, kunkin taulukon elementit eivät ylitä 100, taulukon koko ei ylitä 200 jne. .
Periaate on hyvin yksinkertainen. Tarvitsemme vain taulukon bittejä, joiden koko on summa+1. Taulukon numerot voivat olla vain 0 ja 1. Voimme kuvitella sen hyvin pitkäksi binääribitiksi. int ja Pitkä tyyppi on liian lyhyt, käytämme tässä taulukkoa. Sitten joka kerta, kun taulukon elementti, kuten m, kulkee, binääribittiä siirretään vasemmalle m bitillä ja sitten TAI alkuperäisellä binääribitillä. Määritä lopuksi, onko bits[summa/2] 1, ja palauta tosi, jos se on 1.Tekstin kuvaus ei ole kovin suoraviivainen. Otetaan esimerkki 1 kuvan piirtämiseksi.

Lopuksi löydät säännön, eli niin kauan kuin operaation lopputulos on 1, sitä voidaan yhdistää taulukon elementeillä Niin kauan kuin se on 0, sitä ei voi yhdistää taulukon elementeillä. Ymmärrä yllä oleva prosessi, koodi on helppo kirjoittaa. Koska meidän tarvitsee vain määrittää, onko binääribitin keskiarvo 1, meidän tarvitsee vain laskea matala bitti, eikä korkeaa bittiä tarvitse laskea ollenkaan, koska se siirretään vasemmalle ja korkea. bitillä ei ole mitään vaikutusta keskiarvoon, joten voimme tehdä sen täällä. Pieni optimointi ja lopuksi katsotaan koodia.

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