Opdatering: Læs om at optimere den plads kompleksiteten af dynamisk programmering løsning på mit opfølgende artikel her.,
Ranslen Problem er en virkelig interessant problem i kombinatorik — for at citere Wikipedia,
“givet et sæt af elementer, hver med en vægt og en værdi, bestemme antallet af hvert element at inddrage i en samling, således at den samlede vægt, der er lig med eller mindre end en given grænse, og den samlede værdi er så stor som muligt.”
fra .ikipedia ser vi, at der er et par variationer af Rygsækkeproblemet: 0-1 rygsæk, afgrænset rygsæk og ubegrænset rygsæk., I dag fokuserer vi på den mest almindelige (og enkleste) variation: 0-1 knapsack-problemet.
En lidt mere interessant og relatable frasering af de 0-1 tornyster problem er:
Overvej en tyv kommer ind i et hjem til rob, og han bærer en rygsæk. Der er fast antal varer i hjemmet-hver med sin egen vægt og værdi — smykker, med mindre vægt og højeste værdi vs tabeller, med mindre værdi, men meget tung. For at tilføje brændstof til ilden har tyven en gammel rygsæk, der har begrænset kapacitet., Det er klart, at han ikke kan opdele bordet i halvdelen eller smykker i 3/4ths. Han enten tager det eller forlader det. Kilde
desværre havde jeg svært ved at forstå nogle dele af Hackerearth-artiklen, Hvorfor jeg besluttede at skrive min egen artikel. Denne artikel vil i høj grad være baseret off Hackerearth artikel og kodestykker er skrevet i Java. Jeg vil tacking på yderligere forklaringer og uddybninger, hvor jeg føler, at de er nødvendige.
Vi løser dette problem med dynamisk programmering., Dynamisk programmering kræver en optimal understruktur og overlappende underproblemer, som begge er til stede i 0-1-rygsækkeproblemet, som vi skal se.
det er fint, hvis du ikke forstår, hvad “optimal understruktur” og “overlappende underproblemer” er (det er en artikel til en anden dag). I det væsentlige betyder det bare en bestemt smag af problemer, der giver os mulighed for at genbruge tidligere løsninger til mindre problemer for at beregne en løsning på det aktuelle problem. Du vil se, hvad jeg mener om lidt.,
Problemoplysninger
da dette er 0-1 knapsack-problemet, kan vi enten inkludere et emne i vores rygsæk eller udelukke det, men ikke inkludere en brøkdel af det eller inkludere det flere gange.
løsning
først opretter vi et 2-dimensionelt array (dvs.en tabel) medn + 1rækker ogw + 1 kolonner.
et rækkenummer i repræsenterer sættet af alle elementerne fra række 1— i. for eksempel antager værdierne i række 3, at vi kun har elementer 1, 2 og 3.
et kolonnenummer j repræsenterer Vægtkapaciteten på vores rygsæk., Derfor antager værdierne i kolonne 5 for eksempel, at vores rygsæk kan rumme 5 vægtenheder.
at sætte alt sammen, en post i række i, kolonne j repræsenterer den maksimale værdi, der kan opnås med varer 1, 2, 3 … i, i en rygsæk, der kan indeholde j vægtenheder.
Lad os kalde vores bord mat for matrix. Derfor int mat = new int.
Trin 2:
Vi kan straks begynde at udfylde nogle poster i vores tabel: basissagerne, for hvilke løsningen er triviel., For eksempel på række 0, når vi ikke har nogen varer at vælge imellem, skal den maksimale værdi, der kan gemmes i enhver rygsæk, være 0. Tilsvarende i kolonne 0, for en rygsæk, der kan rumme 0 vægtenheder, er den maksimale værdi, der kan gemmes i den, 0. (Vi antager, at der ikke er masseløse, værdifulde ting.)
Vi kan gøre det med 2 for-løkker:
Trin 3 (kernen af problemet):
Nu, vi ønsker at begynde at befolke vores bord., Som med alle dynamiske programmeringsløsninger vil vi ved hvert trin gøre brug af vores løsninger til tidligere underproblemer.
jeg beskriver først logikken, før jeg viser et konkret eksempel.
forholdet mellem værdien i række i, kolonne j og værdierne til de foregående underproblemer er som følger:
Husk, at vi i række i og kolonne j tackle et underproblem, der består af poster 1, 2, 3 … I med en rygsæk med j kapacitet. Der er 2 muligheder på dette tidspunkt: vi kan enten inkludere punkt i eller ej., Derfor er vi nødt til at sammenligne den maksimale værdi, som vi kan opnå med og uden vare i.
den maksimale værdi, som vi kan opnå uden vare I, kan findes på række i-1, kolonne j. denne del er let. Begrundelsen er ligetil: det maksimum værdi, vi kan få med elementer 1, 2, 3 … jeg skal naturligvis være den samme maksimale værdi, vi kan få med elementer 1, 2, 3 …, i – 1, hvis vi vælger ikke at inddrage elementet i.
for At beregne den maksimale værdi, som vi kan opnå med post jeg, vi først nødt til at sammenligne vægten af varen jeg med ranslen vægt kapacitet., Selvfølgelig, hvis punkt jeg vejer mere end hvad rygsækken kan holde, kan vi ikke medtage det, så det giver ikke mening at udføre beregningen. I dette tilfælde er løsningen på dette problem simpelthen den maksimale værdi, som vi kan opnå uden punkt i (dvs.værdien i rækken ovenfor, i samme kolonne).
Antag dog, at varen jeg vejer mindre end rygsækkens kapacitet. Vi har således muligheden for at inkludere det, hvis det potentielt øger den maksimale opnåelige værdi., Den maksimale opnåelige værdi ved at inkludere vare i er således = værdien af vare i selv + den maksimale værdi, der kan opnås med den resterende kapacitet af rygsækken. Vi ønsker naturligvis at udnytte kapaciteten i vores rygsæk fuldt ud og ikke lade den resterende kapacitet gå til spilde.
derfor vælger vi på række i og kolonne j (som repræsenterer den maksimale værdi, vi kan opnå der), enten den maksimale værdi, som vi kan opnå uden punkt i, eller den maksimale værdi, som vi kan opnå med punkt i, alt efter hvad der er større.
Her er et konkret eksempel på, hvad jeg mener.,
På række 3 (punkt 2), og kolonne 5 (rygsæk kapacitet på 4), kan vi vælge enten at omfatte punkt 2 (som vejer 4 enheder) eller ej. Hvis vi vælger ikke at inkludere det, er den maksimale værdi, vi kan opnå, den samme, som hvis vi kun har punkt 1 at vælge imellem (som findes i rækken ovenfor, dvs.0)., Hvis vi vil inkludere vare 2, er den maksimale værdi, vi kan opnå med vare 2, værdien af vare 2 (40) + den maksimale værdi, vi kan opnå med den resterende kapacitet (som er 0, fordi rygsækken allerede er helt fuld).
På række 3 (punkt 2) og kolonne 10 (knapsack kapacitet på 9) kan vi igen vælge at inkludere punkt 2 eller ej. Hvis vi vælger ikke at gøre det, er den maksimale værdi, vi kan opnå, den samme som i rækken ovenfor i samme kolonne, dvs.10 (ved kun at inkludere punkt 1, som har en værdi på 10). Hvis vi inkluderer punkt 2, har vi en resterende rygsæk kapacitet på 9 – 4 = 5., Vi kan finde ud af den maksimale værdi, der kan opnås med en kapacitet på 5 ved at se på rækken ovenfor i kolonne 5. Således er den maksimale værdi, vi kan opnå ved at inkludere punkt 2, 40 (værdien af punkt 2) + 10 = 50.
Vi vælger det største af 50 vs 10, og så er den maksimale værdi, vi kan opnå med varer 1 og 2, med en rygsæk kapacitet på 9, 50.,
Den algoritme, der kan udtrykkes i Java som dette:
Trin 4 (final solution):
Når tabellen er udfyldt, vil den endelige løsning kan findes på den sidste række i den sidste kolonne, som repræsenterer den maksimale værdi, der fås med alle de elementer og den fulde kapacitet af rygsækken.
return mat;
Arbejde-kode:
Bemærk: her, jeg udskrevet den endelige svar i stedet for at sende det tilbage, da alt ligger under public static void main.,
Thanks for reading!