Problem med programmerings oppgave, Hjelp!

[nufan81]

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..

[Frank2004]

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..

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.

[nufan81]

En grådig algortime som velger støreste tallet, så lenge den ikke overstiger havlparten vil ikke virke...

 

Hvis du skal sjekke alle mulige permutasjoner med alle tall vil ta 2^n tid

[Frank2004]

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.

[Legion]

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

[sygard]

funnet løsningen?

 

..:: Sygard ::..

[sygard]

Har da på en måte løst det med java.

 

Ta en titt: divider.txt

 

..:: Sygard ::..