matematikk.net

Jeg er litt usikker på om det er greit å spørre om dette her fordi er en algoritme-oppgave som jeg lurte på hvordan man løser.

Oppgaven: Hvis du har en liste med tall (array av int) f. eks : {1,2,3,4,6,100} hva er den største "par av summen" du kan få?
Med par av sum menes sum av to delmengder som er like store. Det er ikke nødvendig å bruke opp alle elementer, så du kan la være å bruke noen av tallene dersom det er gunstig.
For eksempel fra listen over er største par av summen {2,6} og {1,3,4}. Fordi 2+6 = 1+3+4. Da er 8 største par av summen det går an å lage og da er svaret 8 i dette tilfellet.

Jeg trenger bare hjelp med å sette opp den rekursive relasjonen.

Jeg skjønner at det er tre valg: inkludere et element i 1. delmengde, inkludere elementet i 2. delmengde, ikke inkludere i noen av delmengdene. Men jeg skjønner ikke helt hvordan det skal føre fram noen steder.

Setter stor pris på all slags hjelp

Det finnes flere måter å angripe dette på, men mye av koding handler om å ta et problem, og bryte det opp i mindre problemer.

Fint eksempel her:

1. Lag en algoritme som finner alle delmengde-summer
2. Sorter resultatene etter sum i synkende rekkefølge
3. Løp gjennom resultatlista og stopp så fort du finner en repetert sum

Steg 1 her kan brytes opp i enda mindre steg.

Steg 1 er der vi kan introdusere rekursjon, fordi det vi er ute etter er å finne mengdesummen av alle mengdene i potensmengden til tallsettet du starter med. Og potensmengden til en mengde kan defineres rekursivt.

Så det kan se ut som:

1a. Lag en funksjon som gir deg potensmengden til en mengde, definert rekursivt
1b. Finn mengdesummen av alle mengdene i potensmengden

Tusen takk for svaret. Trengte bare litt oppklaring på det med en potensmengde. Jeg visste ikke hva en potensmengde var, så jeg søkte det opp. Usikker på om jeg har forstått det riktig, men hvis jeg har forstått dette riktig, så ser jeg et problem.

La listen være {1,2,3,3}.

Da vil {1,2,3} og {3,3} vil være i potensmengden. 1+2+3 = 3+3, så svaret ifølge denne algoritmen være 6.
Men problemet er at vi bruker samme 3-ern i begge delmengder. Så fasit svar er egentlig 3, mens vi får 6.

Noen forslag til hvordan man kan løse dette? (hvis det i det hele tatt er et problem).

Ah, ja jeg tror ikke du nevnte det kriteriet innledningsvis.

Du må i så fall skille de to 3erne ved hjelp av indeksen de ligger på. I lista [1, 2, 3, 3] vil de ha indeks på 2 og 3 respektivt.

Men du må være forsiktig med terminologien her. Slik du har presentert oppgaven, så ser det ut som en oppgave innen mengdelære. Du bruker også {krøllparentes} som er slik vi representerer mengder på listeform. Men repeterte elementer er ikke en ting i mengder. De har per definisjon kun unike elementer.

Hvis du har "oversatt" oppgaven med egne ord, så kan det være nyttig å copy/paste oppgaven ordrett i stedet.