Murtoreppu-ongelma C++:ssa viittaa tavan tunnistamiseen, jolla pussi täytetään tietyn painoisilla ja tuottoisilla esineillä siten, että pussi sisältää maksimiarvon ylittämättä enimmäisrajaa.
Murtoreppu-ongelman ratkaiseminen C++:ssa
Kun annetaan tavarasarja, joilla kullakin on annettu paino ja voitto, määritä jokainen tavaramäärä sellaisessa yhdistelmässä, että tavaroiden kokonaispaino on pienempi kuin pussin enimmäisraja, mutta arvo on pidettävä mahdollisimman suurena.
Algoritmi murtoreppu-ongelman toteuttamiseksi
Knapsack-algoritmin toiminta voidaan ymmärtää seuraavien kohtien kautta:
- Ota kaksi paino- ja voittotaulukkoa.
- Aseta säkin enimmäisarvoksi W.
- Määritä tiheys ottamalla molempien parametrien suhde.
- Lajittele kohteet tiheyden mukaan laskevaan järjestykseen.
- Lisää arvoja, kunnes se on <=W.
Ahne lähestymistapa murtoreppu-ongelman ratkaisemiseen
Ahne lähestymistapa pyrkii tekemään ihanteellisia valintoja jokaisessa vaiheessa, mikä johtaa ihanteelliseen ratkaisuun lopussa. Se ratkaisee ongelmat askel askeleelta ja johtaa johtopäätöksiin sen sijaan, että päättäisi tulokset vain lopussa. Tämä on lähdekoodi murto-reppuongelman ratkaisun toteuttamiseen C++:ssa:
#include
käyttämällä nimiavaruus std ;
struct Esine {
int arvo, paino ;
Esine ( int arvo, int paino )
: arvo ( arvo ) , paino ( paino )
{
}
} ;
bool cmp ( struct Objekti x, struct Objekti y )
{
kaksinkertainen A1 = ( kaksinkertainen ) x. arvo / x. paino ;
kaksinkertainen A2 = ( kaksinkertainen ) ja. arvo / ja. paino ;
palata A1 > A2 ;
}
kaksinkertainen murto-osareppu ( struct Objektin arr [ ] ,
int SISÄÄN, int koko )
{
järjestellä ( arr, arr + koko, cmp ) ;
int curWeight = 0 ;
kaksinkertainen lopullinen arvo = 0,0 ;
varten ( int i = 0 ; i < koko ; i ++ ) {
jos ( curWeight + arr [ i ] . paino <= SISÄÄN ) {
curWeight + = arr [ i ] . paino ;
lopullinen arvo + = arr [ i ] . arvo ;
}
muu {
int jäädä jäljelle = SISÄÄN - curWeight ;
lopullinen arvo + = arr [ i ] . arvo
* ( ( kaksinkertainen ) jäädä jäljelle
/ arr [ i ] . paino ) ;
tauko ;
}
}
palata lopullinen arvo ;
}
int sisään = 60 ;
Objektin arr [ ] = { { 100 , kaksikymmentä } ,
{ 380 , 40 } ,
{ 140 , 10 } ,
{ 180 , 30 } } ;
int koko = koko ( arr ) / koko ( arr [ 0 ] ) ;
cout << 'Maksimi voitto ='
<< murto-osareppu ( arr, v, koko ) ;
palata 0 ;
}
Tässä koodissa määritellään objektirakenne, johon on tallennettu paino- ja voittoarvot. Bool cmp() -funktiota käytetään kahden objektin vertailuun kahden objektin painon ja arvon suhteen perusteella. Taulukko on järjestetty laskevaan järjestykseen ja arvoa lisätään, kunnes se saavuttaa maksiminsa. Jos nykyinen arvo on sallittu ja rajojen sisällä, se lisätään, muuten sen alennettu suhde lisätään pussiin. Painon ja arvon suuruus syötetään pääkoodiin ja maksimivoitto tulostetaan.
Välipalaan tallennettu enimmäisvoitto on 580.
Johtopäätös
Murtoreppu-ongelma C++:ssa viittaa tavan tunnistamiseen, jolla pussi täytetään tietyn painoisilla ja tuottoisilla esineillä siten, että pussi sisältää maksimiarvon ylittämättä enimmäisrajaa. Tämä voidaan saavuttaa ahneella lähestymistavalla, joka pyrkii tekemään ihanteellisia valintoja jokaisessa vaiheessa, mikä johtaa ihanteelliseen ratkaisuun lopussa.