Gå til innhold

Problem med programmerings oppgave, Hjelp!


Anbefalte innlegg

Suppose we are given a set of n positive integers. Our task is to arrange these integers into two piles, or "bins", so that the sum of the integers in one pile is equal to the sum of the integers in the other pile.

For example, given the integers

 

(19, 23, 32, 42, 50, 62, 77, 88, 89, 105, 114, 123, 176)

These numbers sum to 1000. Can they be divided into two bins, bin A and bin B, such that the sum of the integers in each bin is 500?

 

Klare noen å gjøre denne oppgaven bedre enn O(2^n)?? jeg klarer kun O(2^n),

Noen som har løsningen?? finner ikke helt ut hvordan jeg kan løse den rekursivt, så derfor klarer jeg ikke gjøre den dynamisk heller...blir gaaaal.. :dribble:

Lenke til kommentar
Videoannonse
Annonse
  nufan81 skrev:
Suppose we are given a set of n positive integers. Our task is to arrange these integers into two piles, or "bins", so that the sum of the integers in one pile is equal to the sum of the integers in the other pile.

For example, given the integers

 

(19, 23, 32, 42, 50, 62, 77, 88, 89, 105, 114, 123, 176)

These numbers sum to 1000. Can they be divided into two bins, bin A and bin B, such that the sum of the integers in each bin is 500?

 

Klare noen å gjøre denne oppgaven bedre enn O(2^n)?? jeg klarer kun O(2^n),

Noen som har løsningen?? finner ikke helt ut hvordan jeg kan løse den rekursivt, så derfor klarer jeg ikke gjøre den dynamisk heller...blir gaaaal.. :dribble:

Hmm.. Vanskelig å bruke dynamisk programmering her, tror jeg. Ser ikke hvordan du kan dele dette opp i delproblemer, da du ikke kan vite om settet du har plukket ut er med i løsningen før du når 500 eller evt. går over.

 

Selv ser jeg ingen bedre løsning enn å begynne med 176, altså det største tallet, så du kommer over grensen tidligst mulig og kan avbryte rekursjonen, og så lage permutasjoner av tallene som blir igjen.

Lenke til kommentar
  nufan81 skrev:
Hvis du skal sjekke alle mulige permutasjoner med alle tall vil ta 2^n tid

Ikke alle nei, men alle under en viss cutoff. Blir fortsatt ingen effektiv algoritme, selvsagt, men du får fjernet en del kombinasjoner.

 

Mulig du kan redusere kompleksiteten noe ved å skille mellom partall og oddetall, men det er litt for tidlig på dagen til at jeg orker gå videre på den banen.

Lenke til kommentar

tenker litt høyt

-rekursjon og backtracking

 

start med høyeste verdi og legg til nest høyeste osv, overstiger summen 500, så fjerner man det siste tallet og velger neste osv. dersom man etter en gjennomgang av settet får en løsning, fjernes igjen det siste tallet og algoritmen fortsetter.

 

blir vel en løsning bassert på 3-4 stacker

 

Frank2004 var jo inne på løsningen i si første post

Lenke til kommentar
  • 4 måneder senere...

Opprett en konto eller logg inn for å kommentere

Du må være et medlem for å kunne skrive en kommentar

Opprett konto

Det er enkelt å melde seg inn for å starte en ny konto!

Start en konto

Logg inn

Har du allerede en konto? Logg inn her.

Logg inn nå
×
×
  • Opprett ny...