DP-knapsacklösning, fast med vektor istället för matris?
Har en uppgift som ser ut såhär
(OBS: Antalet av varje "guldtackstyp" är oändligt)
Jag har sett många DP knapsack lösningsexempel, men alla knapsacklösningar använder en matris för att lösa problemet. Denna funktion returnerar istället en vektor med int-par som element. Hur ska man tänka här? Hur börjar man skriva en DP knapsacklösning utan att använda en matris (det står ingenstans explicit att man inte kan använda en matris, men med tanke på att returtypen är en vektor så tror jag att det är det dem antyder)? Jag tänker att indexet av vektorn är menat att vara knapsackvikten och int-värdena i elementparet är menade att vara "acc value" och "gold weight". Är jag på rätt spår? Om detta är fallet så låter det också lite ologiskt. Med en matris så har jag två indexpekare (i och j) och ett elementvärde. Här har jag då en indexpekare (knapsackvikten) och två elementvärden (i form av ett int-par). Är det ens möjligt att lösa det på det sättet?
Har också några andra funderingar:
- Vad exakt är den "optimala guldtackan" som dem nämner? De förklarar hur man kan få fram lösningen genom att använda den "optimala guldtackan" (vikten längst till höger i tabellen), men dem förklarar aldrig hur man får fram det värdet. Hur vet jag t.ex. att den optimala guldtackan/vikten vid knapsackvikt 43 i tabellen är 17? De nämner det som att det våre en självklarhet? Missar jag någonting uppenbart?
- Hur vet jag hur många av en guldtackstyp jag måste ta? T.ex. i sista meningen av instruktionen säger dem att de tar 3 guldtackor (1*17 + 2*13). Hur vet jag när jag ska sluta ta guldtackor med vikt 13? Dvs, hur vet jag att jag ska sluta vid 2? Hur vet jag att just 1*17 + 2*13 är den optimala kombinationen?
Förlåt om dessa frågor verkar dumma... jag är bara ganska förvirrad och vet inte riktigt var jag ska börja (och förlåt för den långa texten).
(Skulle såklart fråga mina lärare om jag kunde, men pga Coronaviruset så sitter jag just nu i karantän hemma och ingen hjälp verkar erbjudas just nu medan skolan är upptagen med att gå över till onlineundervisning)
Tack!
Det var ett tag sedan jag läste optimering, men kappsäcksproblemet handlar väl om att man har ett villkor, och så ska du maximera under detta villkor. I ditt fall har du en vikt som kappsäcken kan ta och du har en map med vikt och värde på olika guldtackor. Du vill alltså få ned guldtackor som är värda så mycket som möjligt, men som totalt inte väger mer än kappsäcksvikten.
Som jag förstår det handlar tabellen om att givet att knappsackweight är ett visst värde, ska du välja som första tacka den som väger enligt "gold bar weight". I deras exempel har de 43 som knapsackweight och därför väljer de en som väger 17. Om de då väljer en som väger 17 har de 43-17 = 26 kvar som kapacitet i kappsäcken. Då kollar de helt enkelt på raden där det står 26, väljer en tacka som väger 13 (fås från högra kolumnen på den raden) och går sedan till raden där det står 26-13=13 och läser att de ska ta en som väger 13. Då har de 13-13=0 i kapacitet kvar.
Då har de alltså först tagit en som väger 17, sen en som vägde 13 och sist en som vägde 13.
Mittenkolumen anger det maximala värdet man kan få med sig med denna knappsackweight
Tillägg: Vad du returnerar verkar för mig vara sekvensen av vikter som du valt och deras ackumulerade värden. Så för exemplet lägger du först till ett pair med 17 och 28, sen 13 och 28+21=49, och sist 13 och 49+21=70.
Hondel skrev:Det var ett tag sedan jag läste optimering, men kappsäcksproblemet handlar väl om att man har ett villkor, och så ska du maximera under detta villkor. I ditt fall har du en vikt som kappsäcken kan ta och du har en map med vikt och värde på olika guldtackor. Du vill alltså få ned guldtackor som är värda så mycket som möjligt, men som totalt inte väger mer än kappsäcksvikten.
Som jag förstår det handlar tabellen om att givet att knappsackweight är ett visst värde, ska du välja som första tacka den som väger enligt "gold bar weight". I deras exempel har de 43 som knapsackweight och därför väljer de en som väger 17. Om de då väljer en som väger 17 har de 43-17 = 26 kvar som kapacitet i kappsäcken. Då kollar de helt enkelt på raden där det står 26, väljer en tacka som väger 13 (fås från högra kolumnen på den raden) och går sedan till raden där det står 26-13=13 och läser att de ska ta en som väger 13. Då har de 13-13=0 i kapacitet kvar.
Då har de alltså först tagit en som väger 17, sen en som vägde 13 och sist en som vägde 13.
Mittenkolumen anger det maximala värdet man kan få med sig med denna knappsackweight
Yes, det förstår jag också. Problemet är att "gold bar weight" inte är givet som det är i tabellen. När jag kommer till knapsackvikt 43 så vet jag inte vad "gold bar weight" ska ha för värde. Hur vet dem att den optimala gold bar vikten vid knapsackvikt 43 är just 17 och inte något annat tal? Hur får dem fram det? Dem säger att 17 är det optimala värdet vid knapsackvikt 43 som om det våre en självklarhet, men jag har ingen aning hur dem fick fram siffran 17.
Sammanfattat: Hur avgör man vad den optimala goldbarvikten ska vara?
Hm, när jag läser igen tror jag att jag ändrar mig litegrann.
Funktionen tar in ett tal N. I uppgiften står sen att du ska itererar över alla tal från 1 till N. Jag tolkar det därför som att du ska bygga upp tabellen själv. För säg exempelvis att du har tabellen upp till och med 42, och du vill ha 43:an. Då kan du ju bara gå igenom weights_and_values och för varje par (w,v) där w är weight och v value se vad blir v + (accumulated value för knappsackweight 43-w).
Du får helt enkelt börja med 1, sen börja bygga tabellen själv och utnyttja dina tidigare beräkningar för att göra detta.
Ena komponenten i paren som du returnerar blir då istället optimala ackumulerade värdena för knappsackweights 1,2,...,N. Den andra har jag lite svårt att tolka, jag gissar dock att det är talet som står i högra spalten. Du ska alltså returnera den här tabellen (utan första kolumnen som på något sätt blir inbyggt om du stoppar in paren i ordning. Då kanske du ska iterera över 0 till N istället dock...) Edit: du kan ju också initialisera med ett pair<int,int>{0,0} i vektor och sedan itererar över 1 till N
Hondel skrev:Du får helt enkelt börja med 1, sen börja bygga tabellen själv och utnyttja dina tidigare beräkningar för att göra detta.
Ena komponenten i paren som du returnerar blir då istället optimala ackumulerade värdena för knappsackweights 1,2,...,N. Den andra har jag lite svårt att tolka, jag gissar dock att det är talet som står i högra spalten. Du ska alltså returnera den här tabellen (utan första kolumnen som på något sätt blir inbyggt om du stoppar in paren i ordning. Då kanske du ska iterera över 0 till N istället dock...)
Denna del fattar jag redan.
För säg exempelvis att du har tabellen upp till och med 42, och du vill ha 43:an. Då kan du ju bara gå igenom weights_and_values och för varje par (w,v) där w är weight och v value se vad blir v + (accumulated value för knappsackweight 43-w).
Det är dock detta problem (subproblem) som jag har svårt att förstå och lösa. Du säger att jag ska kolla värdet av "v + (accumulated value för knappsackweight 43-w)", men jag vet ju inte än vad "accumulated value för knappsackweight 43" är (ännu). Det är okänt (... eller?). Är du säker på att du inte menar "accumulated value för knappsackweight 42". När jag kommer till knappsackweight 43 så har jag ju ännu ingen information om acculumulated value vid 43 (eller har jag missuppfattat något). Vad gör sedan när jag räknar ut detta värde (v + (accumulated value för knappsackweight 43-w))? Kollar jag vilket par (av alla par) som ger störst uträknat värde och sedan väljer w av detta par att bli mitt optimala "gold bar weight" för knapsackweight 43?
Nide skrev:För säg exempelvis att du har tabellen upp till och med 42, och du vill ha 43:an. Då kan du ju bara gå igenom weights_and_values och för varje par (w,v) där w är weight och v value se vad blir v + (accumulated value för knappsackweight 43-w).
Det är dock detta problem (subproblem) som jag har svårt att förstå och lösa. Du säger att jag ska kolla värdet av "v + (accumulated value för knappsackweight 43-w)", men jag vet ju inte än vad "accumulated value för knappsackweight 43" är (ännu). Det är okänt (... eller?). Är du säker på att du inte menar "accumulated value för knappsackweight 42". När jag kommer till knappsackweight 43 så har jag ju ännu ingen information om acculumulated value vid 43 (eller har jag missuppfattat något). Vad gör sedan när jag räknar ut detta värde (v + (accumulated value för knappsackweight 43-w))? Kollar jag vilket par (av alla par) som ger störst uträknat värde och sedan väljer w av detta par att bli mitt optimala "gold bar weight" för knapsackweight 43?
Jag säger att du ska använda 43-w, inte 43. För nej, du vet inte vad det blir för 43, däremot vad det blir för alla talen under 43. Som 43-13=30, 43-14=29 osv. Du vet också hur mycket du får för en guldtacka som väger 13. Så om du vet vad du maximalt kan få när du har 30 kvar som kapacitet så vet du vad du maximalt kan få om du har 43 som kapacitet och börjar med att välja en tacka som väger 13, det blir ju accumulated value för kapacitet 30 + vad du får för tackan som väger 13.
Jag tolkar din sista mening som att du tänkt som jag tänkt i det jag skriver.
En grej jag kom att tänka på när jag löste uppgiften själv var att talet i högra kolumnen inte är helt entydigt vilket man ska välja. Jag menar, om det är 13 + 17 + 13 så spelar det ju ingen roll om jag packar först ned 2 13-tackor och sist en 17-tacka, eller först en 17-tacka och sen 2 13-tackor exempelvis. Men det kanske instruktionerna säger vilket man ska välja.
Hondel skrev:Nide skrev:För säg exempelvis att du har tabellen upp till och med 42, och du vill ha 43:an. Då kan du ju bara gå igenom weights_and_values och för varje par (w,v) där w är weight och v value se vad blir v + (accumulated value för knappsackweight 43-w).
Det är dock detta problem (subproblem) som jag har svårt att förstå och lösa. Du säger att jag ska kolla värdet av "v + (accumulated value för knappsackweight 43-w)", men jag vet ju inte än vad "accumulated value för knappsackweight 43" är (ännu). Det är okänt (... eller?). Är du säker på att du inte menar "accumulated value för knappsackweight 42". När jag kommer till knappsackweight 43 så har jag ju ännu ingen information om acculumulated value vid 43 (eller har jag missuppfattat något). Vad gör sedan när jag räknar ut detta värde (v + (accumulated value för knappsackweight 43-w))? Kollar jag vilket par (av alla par) som ger störst uträknat värde och sedan väljer w av detta par att bli mitt optimala "gold bar weight" för knapsackweight 43?
Jag säger att du ska använda 43-w, inte 43. För nej, du vet inte vad det blir för 43, däremot vad det blir för alla talen under 43. Som 43-13=30, 43-14=29 osv. Du vet också hur mycket du får för en guldtacka som väger 13. Så om du vet vad du maximalt kan få när du har 30 kvar som kapacitet så vet du vad du maximalt kan få om du har 43 som kapacitet och börjar med att välja en tacka som väger 13, det blir ju accumulated value för kapacitet 30 + vad du får för tackan som väger 13.
Jag tolkar din sista mening som att du tänkt som jag tänkt i det jag skriver.
En grej jag kom att tänka på när jag löste uppgiften själv var att talet i högra kolumnen inte är helt entydigt vilket man ska välja. Jag menar, om det är 13 + 17 + 13 så spelar det ju ingen roll om jag packar först ned 2 13-tackor och sist en 17-tacka, eller först en 17-tacka och sen 2 13-tackor exempelvis. Men det kanske instruktionerna säger vilket man ska välja.
Då menar du alltså "v + accumulated value för (43-w)" och inte "v + ((accumulated value för 43) - w )" (ser du skillnaden?). Jag läste då det du skrev tidigare på fel sätt eftersom att du inte la några paranteser runt "43-w". Men jag tror jag har fattar nu (om det är så att du menade "v + accumulated value för (43-w)"). Har jag förstått dig rätt nu?
Ordningen av hur man tar guldtackorna tror jag inte spelar någon roll. Uträkningen är kommutativ ändå.
