En mängd med ett jämnt antal (2N) element, vart och ett med ett positivt "mått", skall delas upp i två lika stora mängder (N element) så att summan av måtten är så lika som möjligt i de två mängderna.

Finns någon effektiv metod/algoritm för detta? Eller måste i princip alla kombinationer testas?

Finns möjligen en effektiv metod som ger en god - men inte nödvändigtvis optimal - lösning?

Utan något bevis (ännu) känns det som om följande skulle kunna fungera.

Sortera, ta från toppen och lägg konsekvent i minsta högen.

Edit: missade att det skall vara lika många i varje hög.

Det känns som att man skulle kunna använda en glupsk algoritm på något vis.

Det låter hyfsat mycket som det vanliga "brädproblemet"; man har ett antal brädor som man vill dela upp i m stycken bitar, vardera med storlek x_i, 1<=i<=m. Vilket är det minsta N (där N är antalet brädor) som detta går att lösa för?

En ide du kan försöka spinna vidare på annars:
1. Sortera.
2. Ta varannan (hyfsat bra redan där)
3. Skyffla fram och tillbaka på något smart sätt, för att minimera skillnaden.
Kanske bara loopa igenom vänster och höger och försöka hitta den differens som ligger närmast den som redan är?

Blir N^2 då.
Och du kan ju göra det flera gånger, säg M; så får du M*N^2, där du själv väljer M.

(Det blir ju naturligtvis en approximativ lösning, men den borde ge hyfsade resultat.

Nåväl, chefen tyckte att den aktuella lösningen med att pröva olika kombinationer duger. För N=5 tar den under en sekund och större N är mycket ovanligt. Kan möjligen effektivisera den något.

Rent instinktivt svarar jag att det borde gå rätt bra att lösa med någon form av best-first sökning som använder hurpass lika summorna i de båda mängderna är som heurestik.

Jag skulle sortera och ta varannan, sedan skulle jag byta ut det minsta elementet i den minsta högen med det största ur den största (varje element får bara byta plats en gång) tills jag har två lika stora högar alternativt har bytt samtliga element. Det borde enligt min mening vara samma sak som att testa alla kombinationer men att struktuera testen så att överflödiga test är onödiga.