Oppdatering: Les om optimalisering av plass kompleksiteten av dynamisk programmering løsning i min oppfølging artikkelen her.,
Vesken er Problemet en virkelig interessant problem i kombinatorikk — for å sitere Wikipedia,
«gitt et sett av elementer, hver med en vekt og en verdi, bestemme antall av hvert element for å inkludere i en samling, slik at den totale vekten er mindre enn eller lik en gitt grense, og den totale verdien er så stor som mulig.»
Fra Wikipedia, ser vi at det er noen varianter av Vesken Problem: 0-1 niste, avgrenset av niste, og ubegrensede niste., I dag skal vi fokusere på de mest vanlige (og enkleste) variant: den 0-1 niste problem.
En litt mer interessant og relatable utformingen av 0-1 niste problemet er:
Vurdere en tyv kommer inn i et hjem å rane og han bærer en ryggsekk. Det er fast antall elementer i hjem — hver med sin egen vekt og verdi — Smykker, med mindre vekt og høyeste verdi vs tabeller, med mindre verdi, men mye tung. For å legge bensin på bålet, tyven har en gammel ryggsekk som har begrenset kapasitet., Åpenbart, han kan ikke dele bord i halvparten eller smykker til 3/4ths. Han enten tar det eller forlater det. Kilde
Dessverre, jeg hadde litt problemer med å forstå noen deler av Hackerearth artikkelen, som er grunnen til at jeg bestemte meg for å skrive min egen artikkel. Denne artikkelen vil i stor grad bli basert på Hackerearth artikkel og kodebiter er skrevet i Java. Jeg skal overvinne på ytterligere forklaringer og noko der jeg føler de er nødvendige.
Vi vil løse dette problemet med dynamisk programmering., Dynamisk programmering krever en optimal underlaget og overlappende sub-problemer, som begge er til stede i 0-1 niste problem, som vi skal se.
Det er greit hvis du ikke forstår hva «optimal underlaget» og «overlappende sub-problemer» er (det er en artikkel for en annen dag). I hovedsak, det betyr bare en spesiell smak av problemer som tillater oss å gjenbruke tidligere løsninger til mindre problemer for å beregne en løsning på det aktuelle problemet. Du vil se hva jeg mener i en bit.,
Problemet detaljer
Siden dette er den 0-1 niste problem, vi kan enten ta et element i vår niste eller utelukke det, men inkluderer ikke en brøkdel av det, eller ta det flere ganger.
– Løsning
Først oppretter vi en 2-dimensjonal array (dvs. en tabell) av n + 1 rader og w + 1 kolonner.
En rad nummer jeg representerer mengden av alle elementer fra rad 1— jeg. For eksempel, verdier i rad 3 forutsetter at vi bare har elementer 1, 2, og 3.
En kolonne nummer j representerer vekt kapasitet på våre niste., Derfor er verdiene i kolonne 5, for eksempel, tar utgangspunkt i at vår niste kan holde 5 vekt enheter.
å Sette alt sammen, er det en oppføring i rad jeg, kolonne j representerer den maksimale verdien som kan oppnås med punktene 1, 2, 3 … jeg, i en ryggsekk som kan holde j vekt enheter.
La oss kalle vårt bord mat for matrix. Derfor, int mat = new int.
Trinn 2:
Vi kan umiddelbart begynne å fylle noen oppføringer i vår tabell: base tilfeller, der løsningen er trivielt., For eksempel, på rad 0, når vi har noen elementer for å plukke fra, er den maksimale verdien som kan lagres i en ryggsekk må være 0. På samme måte, i kolonne 0, for en ryggsekk, som kan romme 0 vekt-enheter, er den maksimale verdien som kan være lagret i det er 0. (Vi antar at det ikke er noen massless, verdifulle elementer.)
Vi kan gjøre dette med 2 løkker:
Trinn 3 (kjernen av problemet):
Nå, ønsker vi å begynne å fylle bordet vårt., Som med alle dynamisk programmering løsninger, på hvert trinn, vil vi gjøre bruk av våre løsninger for tidligere bi-problemer.
jeg vil først beskrive logikk, før du viser et konkret eksempel.
forholdet mellom verdien på rad jeg, kolonne j og verdiene til forrige sub-problemer er som følger:
Husker at på rad i og kolonne j, vi takler et sub-problemet som består av elementene 1, 2, 3 … jeg med en ryggsekk av j kapasitet. Det er 2 alternativer på dette punkt: vi kan enten ta element jeg eller ikke., Derfor trenger vi å sammenligne den maksimale verdien som vi kan få med og uten element jeg.
Den maksimale verdien som vi kan få tak i uten element jeg kan bli funnet på rad i-1, kolonne j. Denne delen er lett. Begrunnelsen er enkel: det maksimale verdien vi kan få med punktene 1, 2, 3 … jeg må selvfølgelig være den samme maksimale verdien vi kan få med punktene 1, 2, 3 … jeg – 1, hvis vi velger ikke å inkludere element jeg.
for Å beregne den maksimale verdien som vi kan få med element jeg, vi må først for å sammenligne vekten av elementet jeg med skreppen vekt kapasitet., Selvfølgelig, hvis elementet jeg veier mer enn hva skreppen kan holde, vi kan ikke ta det, så gir det ikke mening å utføre beregningen. I så fall er løsningen på dette problemet er ganske enkelt den maksimale verdien som vi kan få tak i uten element jeg (dvs. verdien i raden ovenfor, på samme kolonne).
Likevel, la oss anta at elementet jeg veier mindre enn skreppen kapasitet. Vi har dermed muligheten til å ta det, hvis det potensielt øker maksimal oppnåelig verdi., Maksimalt oppnåelig verdi ved å inkludere element jeg er således = verdien av elementet jeg selv + den maksimale verdien som kan oppnås med de gjenværende kapasitet i skreppen. Vi tydeligvis ønsker å gjøre full bruk av kapasiteten på vår niste, og ikke la noen gjenværende kapasitet gå til avfall.
Derfor, i rad i og kolonne j (som representerer den maksimale verdien som vi kan få tak i det), ville vi plukke enten den maksimale verdien som vi kan få tak i uten element jeg, eller den maksimale verdien som vi kan få med element jeg, som er større.
Her er et konkret eksempel på hva jeg mener.,
På rad 3 (punkt 2), og kolonne 5 (niste kapasitet på 4), kan vi velge å enten ta med punkt 2 (som veier 4 enheter) eller ikke. Hvis vi velger ikke å inkludere det, er den maksimale verdien vi kan få tak i er det samme som om vi bare har element 1 for å velge mellom (som er funnet i raden ovenfor, dvs. 0)., Hvis vi ønsker å ta med punkt 2, er den maksimale verdien vi kan få med punkt 2 er verdien av punkt 2 (40) + den maksimale verdien vi kan oppnå med de gjenværende kapasitet (som er 0, fordi vesken er helt full allerede).
På rad 3 (punkt 2), og kolonne 10 (niste kapasitet av 9), igjen, kan vi velge å enten ta med punkt 2 eller ikke. Hvis vi velger ikke å gjøre det, er den maksimale verdien vi kan få tak i er den samme som i raden over på den samme kolonnen, dvs. 10 (ved å inkludere kun punkt 1, som har en verdi av 10). Hvis vi inkluderer punkt 2, vi har en gjenværende niste kapasitet på 9 – 4 = 5., Vi kan finne ut den maksimale verdien som kan oppnås med en kapasitet på 5 ved å se på rad ovenfor, kolonne 5. Dermed maksimal verdi vi kan oppnå ved blant annet punkt 2 er 40 (verdien av element 2) + 10 = 50.
Vi plukke den største av 50 vs 10, og så er den maksimale verdien vi kan få med punkt 1 og 2, med en ryggsekk kapasitet på 9, er 50.,
algoritmen kan bli uttrykt i Java som dette:
Trinn 4 (endelige løsningen):
Når bordet har vært befolket, den endelige løsningen kan bli funnet i den siste raden i den siste kolonnen, som representerer den maksimale verdien som er oppnåelig med alle elementene og full kapasitet på vesken.
return mat;
Arbeide koden:
Merk: her er jeg skrevet det endelige svaret i stedet for å vende det, siden alt er plassert under public static void main.,
Thanks for reading!