Teknologian jakaminen

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

yksi,Kaksiulotteinen matriisi

1、tilasiirtymäyhtälö：

• Älä laita esineitä : Päätelty arvosta dp[i - 1][j], eli repun kapasiteetti on j ja kohteen i enimmäisarvoa ei ole asetettu siihen Tällä hetkellä dp[i][j] on dp[i -. 1][j]. (Itse asiassa, kun tuotteen i paino on suurempi kuin repun j paino, tuotetta i ei voi laittaa reppuun, joten repun arvo on edelleen sama kuin ennen.)
• Laita kohde i: dp[i - 1][j - paino[i]] johdettu, dp[i - 1][j - paino[i]] on repun enimmäiskapasiteetti ilman kohtaa i, kun kapasiteetti on j - paino[ i]-arvo, niin dp[i - 1][j - paino[i]] + arvo[i] (kohteen i arvo) on suurin arvo, joka saadaan laittamalla tuote i reppuun

Joten rekursiivinen kaava: dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - paino[i]] + arvo[i]);

2. Alustus

(1) Alkaen dp[i][j]:n määritelmästä, jos repun kapasiteetti j on 0, eli dp[i][0], riippumatta siitä, mitkä kohteet valitaan, repun kokonaisarvo on oltava 0.

(2) Tilasiirtymäyhtälö dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - paino[i]] + arvo[i]); nähdään, että i on johdettu arvosta i-1, joten se on alustettava, kun i on 0.

dp[0][j], eli: i on 0, tallennettaessa nimikenumeroa 0, maksimiarvo, jonka kunkin kapasiteetin reppu voi tallentaa.

Silloin on selvää, että kun j < paino[0], dp[0][j] tulee olla 0, koska repun kapasiteetti on pienempi kuin 0:lla numeroitu tavaran paino.

Kun j >= paino[0], dp[0][j] tulee olla arvo[0], koska repun tilavuus riittää tavaran numeron 0 säilyttämiseen.

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) Muu alaindeksin alustus:

dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - paino[i]] + arvo[i])

dp[1][1] = max(dp[0][1], dp[0][1- paino[i]] + arvo[i]) on oltava sen vasemmalla ja yläpuolella,

Siksi sen on oltava alustettu ja se voidaan asettaa mihin tahansa arvoon mukavuuden vuoksi oletusarvoisesti.

2. Yksiulotteinen (rullaava array)

1. Yksiulotteisessa dp-taulukossa dp[j] tarkoittaa: reppu, jonka kapasiteetti on j, voi kuljettaa tavaroita, joiden enimmäisarvo on dp[j]

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

2. Alustus

(1) dp[0]=0, koska 0-kapasiteetin repussa mukana olevien tavaroiden enimmäisarvo on 0.

(2) Oletetaan, että kohteiden arvo on suurempi kuin 0,Jotta alkuarvo ei korvaisi sitä, niin dpTaulukon alustusKun , ne kaikki ovat aluksi 0

3. Läpikulkujärjestys

Kulje käänteisessä järjestyksessä

Selitys 1: Luettelon lopussa oleva arvo on määritettävä vertaamalla sitä aikaisempaan arvoon, joka on saatu kulkemalla edellisellä tasolla.

Selitys 2: Jokaisessa repussa on vain yksi 01-reppu, joka liittyy edellisen laukun tilaan oikea on nykyisen pussin odottava tila. Koodissa vasemmalla oleva numero vaaditaan oikeanpuoleisen taulukon määrittämiseen, joten vasemmanpuoleista numeroa ei voida tuhota ennen kuin oikeanpuoleinen numero on laskettu.

Selitys 3: Kahden ulottuvuuden kohdalla jokaisen uuden dp-luvun tulos tulee ylhäältä ja vasemmalta, itse asiassa sen pitäisi olla tällainen yhdessä ulottuvuudessa, mutta yhdessä ulottuvuudessa, jos se on edelleen vasemmalta oikealle todellinen vasen Luvut on päivitetty ( Vasen puoli ei ole enää "alkuperäinen" vasen puoli!Tämä aiheuttaa kaksinkertaisen laskennan ), vaikka toppi olisi edelleen alkuperäinen toppi, saatu numero on virheellinen.Ja jos kuljemme reppukerroksessa (sisäkerroksessa) oikealta vasemmalle, vasemmalla oleva elementti tulee ainaSitä ei korvata uusilla arvoilla aiemman toiminnan vuoksi., jotta oikea arvo voidaan saada.

3. Sovellus

1. Annettu ei-tyhjä taulukko, joka sisältää vain positiivisia kokonaislukuja. Onko mahdollista jakaa tämä taulukko kahdeksi osajoukoksi niin, että näiden kahden osajoukon elementtien summa on yhtä suuri?

Huomautus: Kunkin taulukon elementit eivät saa ylittää 100 ja taulukon koko enintään 200

Esimerkki 1:

• Syöte: [1, 5, 11, 5]
• Tulos: tosi
• Selitys: Taulukko voidaan jakaa [1, 5, 5] ja [11]

analysoida:

Tuote on minä,

Paino on numerot[i], arvo on myös numerot[i] ja repun tilavuus on summa/2.

Samanlainen kuin 01 reppu

Tilasiirtymäyhtälö:

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. Siellä on kasa kiviä, ja jokaisen kiven paino on positiivinen kokonaisluku.

Valitse jokaisella kierroksella mitkä tahansa kaksi kiveä ja murskaa ne yhteen. Oletetaan, että kivien painot ovat x ja y, vastaavasti, ja x <= y. Sitten murskauksen mahdolliset tulokset ovat seuraavat:

Jos x == y, niin molemmat kivet murskautuvat täysin;

Jos x != y, niin x-painoinen kivi särkyy kokonaan ja y-painoinen kivi saa uuden painon yx.

Lopulta jäljellä on enintään yksi kivi. Palauttaa tämän kiven pienimmän mahdollisen painon. Jos kiviä ei ole jäljellä, palauta 0.

Esimerkki:

• Syöttö: [2,7,4,1,8,1]
• Lähtö: 1

analysoida:

Yritä jakaa kivet kahteen samanpainoiseen kasaan niin, että pienin jäljelle jäänyt kivi törmäyksen jälkeen

Jaa se sitten kahteen kivipinoon. Yhden kivipinon kokonaispaino on dp[target] ja toisen pinon kokonaispaino on summa - dp[target].

Tavoitetta laskettaessa tavoite = summa / 2, koska se pyöristetään alaspäin, joten summa - dp[tavoite] on oltava suurempi tai yhtä suuri kuin dp[tavoite]

Tällöin törmäyksen jälkeen jäljelle jäävän kiven vähimmäispaino on (summa - dp[kohde]) - dp[kohde]

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

lainattu kohteesta:Code Random Notes