Dela en mängd i två mängder
Hej, alla!
Jag står inför följande problem:
I en mängd M finns mellan 1 och 20 element. Alla element är heltal mellan 100 och 600. Din uppgift är att fördela alla element i M så jämt du kan i två separata delmängder, sådana att summan av elementen i de två delmängderna skiljer sig så lite det bara går. Output ska vara summan av elementen i respektive delmängd.
Jag har redan löst det genom att skapa en lista med alla möjliga summor som går att få av elementen i M. Med den här listan kan jag enkelt (men inte så snabbt) hitta den minsta skillnaden mellan summorna av elementen i de två delmängderna.
Problemet är just att det inte går tillräckligt snabbt när antalet element i M närmar sig 20. Listan av alla möjliga summors längd är över en miljon i det fallet, vilket gör att jag tror att den här metoden är lite ”brute force”. Min algoritm hittar minsta differensen på omkring 10 sekunder, varav nästan hela tiden är hänförlig till att hitta alla möjliga kombinationer av element. Kravet är att algoritmen ska göra det på 2 sekunder.
Frågan jag har är alltså:
Finns det ett bättre sätt att angripa problemet, som leder till snabbare exekvering?
Hur skulle ni angripa problemet?
Är det ens möjligt för ett pythonprogram att fixa det på under 2 sekunder? (Det stod en fritt att välja språk).
Det är alltså ingen specifik kodfråga utan jag är mer nyfiken på vad ni anser vara ett effektivt sätt att lösa uppgiften.
Disclaimer: jag är ny på forumet och på programmering, och hoppas att ni har överseende med att jag inte är helt hundra på alla skrivna och oskrivna regler som gäller på forumet och i programmerarcommunityt i stort.
Hoppas att mitt inlägg gick att förstå och att det bidrar till intressanta samtal.
mvh
Intressant problem. Är det på nån problemlösarsajt?
Jag vet inte om det är exponentiellt (men det kanske går att komma nära på rimlig tid) eller polynomiellt. Din lösning hittar förstås bästa lösningen men på exponentiell tid.
Laguna skrev:Intressant problem. Är det på nån problemlösarsajt?
Jag vet inte om det är exponentiellt (men det kanske går att komma nära på rimlig tid) eller polynomiellt. Din lösning hittar förstås bästa lösningen men på exponentiell tid.
Ja precis från Kattis. Jag formulerade det lite mer koncist bara. Tror du att min metod hade klarat det under två sekunder, hade jag använt mig av java eller c++? Svårt att svara på kanske. På min iMac från 2013 körs mitt pythonprogram på 10 sekunder ungefär.
Måste man hitta optimum, eller är det godkänt om msn t. ex. får skillnaden att bli 5 när den kan bli 3?
Jag konsulterade programmeringsexperten här hemma och fick tipset:
Titta på talen i avtagande ordning.
Laguna skrev:Måste man hitta optimum, eller är det godkänt om msn t. ex. får skillnaden att bli 5 när den kan bli 3?
Nej det skulle inte gillas.
Smaragdalena skrev:Jag konsulterade programmeringsexperten här hemma och fick tipset:
Titta på talen i avtagande ordning.
Det var min första ansats, men det blev inte rätt. Att tilldela den mängd med lägst summa nästa element i listan, dvs. (jag bara gissar att det var metoden som din expert hade i åtanke). Det ger en liten diff, men man får inte optimala lösningar alla gånger. I synnerhet inte då optimum är 0.
Om du vet alla 20 element så kan du beräkna deras totalsumma och således även den optimala delmängdssumman (totalsumman dividerat på 2).
Då kanske problemet blir lite lättare sen, då räcker det att hitta X element ifrån M som så nära som möjligt blir denna summa.
Flezer skrev:Om du vet alla 20 element så kan du beräkna deras totalsumma och således även den optimala delmängdssumman (totalsumman dividerat på 2).
Då kanske problemet blir lite lättare sen, då räcker det att hitta X element ifrån M som så nära som möjligt blir denna summa.
Vet inte om den metoden leder till färre beräkningar. Totalsumman är inte jämnt delbar alla gånger. Tror att man bara hittar approximativa lösningar med den metoden.
Jag misstänker att problemet är NP-fullständigt, och då finns det inga snabba lösningar utom i speciella fall. Jag kan ha fel förstås.
Om man måste använda brute force så kan man kanske göra det på ett smart sätt så att man klarar tidsgränsen. Eller så finns det heuristiska metoder som råkar ge rätt svar för just dessa indata. Är det bestämda indata, eller varierar de? Hmm, man kanske aldrig får se dem, om man ska skicka in programmet och får ett svar. Nej, du sa att du kör på din egen dator.
Har du en länk till problemsidan?
Det ska inte (inte alls!) vara några problem att hinna med 220 på 2s. Du har nog gjort något onödigt tidskrävande i din kod, posta den?
Berty von Fjerty skrev:Finns det ett bättre sätt att angripa problemet, som leder till snabbare exekvering?
Det låter som ett klassiskt dynamisk programmering-problem (googla knapsack problem).
emilg skrev:Berty von Fjerty skrev:Finns det ett bättre sätt att angripa problemet, som leder till snabbare exekvering?
Det låter som ett klassiskt dynamisk programmering-problem (googla knapsack problem).
På Python Pool finns en artikel om tre olika sätt att lösa ett knapsack-problem. Provade den med dynamisk programmering och 20 slumpade värden i olika värdeområden på en i5-4200U@2.3GHz.
10 värden i värdeområdet [1, 1000] löses på ca 40 ms.
10 värden i värdeområdet [1, 10000] löses på 100-200 ms.
10 värden i värdeområdet [1, 100000] löses på 1.5-2.2 s.
20 värden i värdeområdet [1, 1000] löses på ca 100 ms.
20 värden i värdeområdet [1, 10000] löses på 0.6-1.3 s.
20 värden i värdeområdet [1, 100000] löses på 8-14 s.
Så, förutom antal värden så har även värdeområdet en inverkan på exekveringstiden.
EDIT: Utan någon djupare analys verkar antal värden ha en större inverkan, kanske O(n log n)? Värdeområdet verkar ha en linjär påverkan, d v s O(n).
Laguna skrev:Jag misstänker att problemet är NP-fullständigt, och då finns det inga snabba lösningar utom i speciella fall. Jag kan ha fel förstås.
Om man måste använda brute force så kan man kanske göra det på ett smart sätt så att man klarar tidsgränsen. Eller så finns det heuristiska metoder som råkar ge rätt svar för just dessa indata. Är det bestämda indata, eller varierar de? Hmm, man kanske aldrig får se dem, om man ska skicka in programmet och får ett svar. Nej, du sa att du kör på din egen dator.
Har du en länk till problemsidan?
Nej, tyvärr. Det var ett test på en rekryterarsida och länken är privat (och dessutom stängd). Jag har också glömt vad problemet hette :/
Lindehaven skrev:emilg skrev:Berty von Fjerty skrev:Finns det ett bättre sätt att angripa problemet, som leder till snabbare exekvering?
Det låter som ett klassiskt dynamisk programmering-problem (googla knapsack problem).
På Python Pool finns en artikel om tre olika sätt att lösa ett knapsack-problem. Provade den med dynamisk programmering och 20 slumpade värden i olika värdeområden på en i5-4200U@2.3GHz.
10 värden i värdeområdet [1, 1000] löses på ca 40 ms.
10 värden i värdeområdet [1, 10000] löses på 100-200 ms.
10 värden i värdeområdet [1, 100000] löses på 1.5-2.2 s.
20 värden i värdeområdet [1, 1000] löses på ca 100 ms.
20 värden i värdeområdet [1, 10000] löses på 0.6-1.3 s.
20 värden i värdeområdet [1, 100000] löses på 8-14 s.
Så, förutom antal värden så har även värdeområdet en inverkan på exekveringstiden.
EDIT: Utan någon djupare analys verkar antal värden ha en större inverkan, kanske O(n log n)? Värdeområdet verkar ha en linjär påverkan, d v s O(n).
Okej då var det nåt fel jag gjorde. Tack för svar
Berty von Fjerty skrev:Laguna skrev:Jag misstänker att problemet är NP-fullständigt, och då finns det inga snabba lösningar utom i speciella fall. Jag kan ha fel förstås.
Om man måste använda brute force så kan man kanske göra det på ett smart sätt så att man klarar tidsgränsen. Eller så finns det heuristiska metoder som råkar ge rätt svar för just dessa indata. Är det bestämda indata, eller varierar de? Hmm, man kanske aldrig får se dem, om man ska skicka in programmet och får ett svar. Nej, du sa att du kör på din egen dator.
Har du en länk till problemsidan?
Nej, tyvärr. Det var ett test på en rekryterarsida och länken är privat (och dessutom stängd). Jag har också glömt vad problemet hette :/
Jag hoppas rekryteringen var stängd när du postade här?
Provade att slumpa 20 tal mellan 100 och 600 (som i uppgiften) och körde 10 gånger:
Set 1 sum = 3564, set 2 sum = 3565. Took 0.100 s.
Set 1 sum = 2951, set 2 sum = 2952. Took 0.116 s.
Set 1 sum = 3673, set 2 sum = 3674. Took 0.103 s.
Set 1 sum = 3542, set 2 sum = 3542. Took 0.050 s.
Set 1 sum = 3229, set 2 sum = 3229. Took 0.047 s.
Set 1 sum = 3862, set 2 sum = 3862. Took 0.078 s.
Set 1 sum = 3781, set 2 sum = 3781. Took 0.085 s.
Set 1 sum = 2871, set 2 sum = 2872. Took 0.047 s.
Set 1 sum = 3351, set 2 sum = 3351. Took 0.038 s.
Set 1 sum = 3527, set 2 sum = 3528. Took 0.047 s.
