Knapsack-problemet
Jeg fandt Knapsack-problemet vanskeligt og interessant på samme tid. Jeg er sikker på, at hvis du besøger denne side, er du allerede kender problemet, men netop af hensyn til afslutning :
Problem:
i Betragtning af en Rygsæk med en maksimal kapacitet på W og N elementer, hver med sin egen værdi og vægt, smide ting i Rygsækken, så det endelige indhold har den maksimale værdi. Yikes !!,
Her er den generelle måde, problemet forklares på – Overvej at en Tyv kommer ind i et hjem for at røve, 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 lader det
Eksempel :
Knapsack Max weight : W = 10 (units)Total items : N = 4Values of items : v = {10, 40, 30, 50}Weight of items : w = {5, 4, 6, 3}
Et overfladisk kig på eksemplet data fortæller os, at det maksimale værdi, som vi kan rumme, at den grænse på max vægt på 10 er 50 + 40 = 90 med en vægt på 7.
tilgang:
den måde, dette løses optimalt på, bruger dynamisk programmeringsløsning til mindre sæt rygsækproblemer og udvider dem derefter til det større problem.,
lad os bygge et element Weight vægt array kaldet V (Value array):
V = 4 rows * 10 columnshver af værdierne i denne Matri.repræsenterer et mindre rygsæk problem.
Basissag 1 : Lad os tage sagen om 0.kolonne. Det betyder bare, at rygsækken har 0 kapacitet. Hvad kan du holde i dem? Intet. Så lad os fylde dem alle med 0s.
Base case 2 : Lad os tage sagen om 0 række. Det betyder bare, at der ikke er nogen ting i huset. Hvad holder du i din rygsæk, hvis der ikke er nogen ting. Intet igen !!! Alle nuller.,
løsning:
1) Lad os nu begynde at udfylde rækken række. Hvad betyder række 1 og kolonne 1? Det givet det første element (række), kan du rumme det i rygsækken med kapacitet 1 (kolonne). Nej. Vægten af den første vare er 5. Så lad os udfylde 0. Faktisk ville vi ikke være i stand til at udfylde noget, før vi når kolonne 5 (vægt 5).2) Når vi når kolonne 5 (som repræsenterer vægt 5) på den første række, betyder det, at vi kunne rumme vare 1., Lad os fylde i 10 der (husk, at dette er en Værdi, matrix):
3), der Bevæger sig på, for vægt 6 (kolonne 6), kan vi rumme noget andet med de resterende vægten af 1 (vægt – vægten af dette item => 6 – 5). Hej, husk, vi er på det første punkt. Så det er lidt intuitivt, at resten af rækken bare vil være den samme værdi, da vi ikke kan tilføje noget andet element til den ekstra vægt, vi har fået.,
4) så den næste interessante ting sker, når vi når kolonne 4 i tredje række. Den aktuelle løbende vægt er 4.
Vi bør kontrollere for følgende tilfælde.
1) kan vi rumme punkt 2 – Ja, Vi kan. Punkt 2 ‘ s vægt er 4.
2) er værdien for den aktuelle vægt højere uden punkt 2? – Kontroller den forrige række for samme vægt. Nej. den forrige række * har 0 i det, da vi ikke var i stand til at rumme vare 1 i vægt 4.3) kan vi rumme to elementer i samme vægt, så vi kunne maksimere værdien? – Nej., Den resterende vægt efter fradrag af Varen2s vægt er 0.
hvorfor forrige række?
simpelthen fordi den forrige række ved vægt 4 i sig selv er en mindre rygsæk-løsning, der giver den maksimale værdi, der kunne akkumuleres for den vægt indtil det punkt (krydser gennem emnerne).,
Eksemplificerer,
1) værdien af det aktuelle element = 40
2) vægten af det aktuelle element = 4
3) Den vægt, der er tilovers = 4 – 4 = 0
4) Check rækken over (det Punkt ovenfor i tilfælde af Punkt 1 eller den kumulerede Antal værdi i tilfælde af resten af rækker). For den resterende vægt 0, er vi i stand til at rumme vare 1? Kort sagt, er der overhovedet nogen værdi i rækken ovenfor for den givne vægt?,
beregningen lyder således :
1) Tager max værdi for den samme vægt, uden at denne post:
previous row, same weight = 0=> V2) værdien af det aktuelle emne + værdi, som vi kunne rumme de resterende vægt:
Max blandt de to er 40 (0 40).
3) Den næste og vigtigste begivenhed sker i kolonne 9 Og række 2. Det betyder, at vi har en vægt på 9, og vi har to ting. Når vi ser på eksempeldataene, kunne vi rumme de to første elementer., Her overvejer vi få ting:
- værdien af det aktuelle emne = 40
- vægten af det aktuelle emne = 4
- den vægt, der er tilbage = 9 – 4 = 5
- kontroller rækken ovenfor. Ved den resterende vægt 5, er vi i stand til at rumme punkt 1.
Så, beregningen er :
1) Tager max værdi for den samme vægt, uden at denne post:
previous row, same weight = 102) værdien af det aktuelle emne + værdi, som vi kunne samle med de resterende vægt:
Value of current item (40)+ value in previous row with weight 5 (total weight until now (9) - weight of the current item (4))= 1010 vs 50 = 50.,
i slutningen af løse alle disse mindre problemer, vi skal bare returnere den værdi, V – Punkt 4 på Vægt 10:
Kompleksitet
at Analysere kompleksiteten af løsningen er ret straight-forward. Vi har bare en loop for within inden for en loop af N => O (N O)
implementering:
Her kommer den obligatoriske implementeringskode i Java: