Alle combinaties die een som opleveren

[creator1988]

Ik heb een array met getallen, en een som die ik wil bereiken. Bijvoorbeeld:

[ 10, 10, 10, 10, 10, 10, 10, 50 ]

en de som moet worden: 70.

Mogelijke combinaties zijn daar dan: [ 10, 10, 50 ] en [ 10, 10, 10, 10, 10, 10, 10 ].

Hoe genereer ik die een beetje snel?

[HMS]

Knapsack problem: Wikipedia: Knapsack problem

~edit:

Behalve dat je hier dan alle mogelijkheden wil hebben, en niet alleen de eerste de beste. Maar komt in principe op hetzelfde neer. Denk wel dat je snel naar bruteforce moet grijpen.

Dit probleem is overigens wel NP-hard / compleet.

[ Voor 56% gewijzigd door HMS op 30-07-2012 20:09 ]

[leuk_he]

HMS is me al voor.

in dit geval:
hoe groot is de array?
Is de ene 10 gelijk aan de andere 10? dan kun je de array verkleinen ([ 5x 10], [1x50]) en neemt je aantal mogelijkheden af.
array sorteren van groot naar klein, dan en eerst de grote getallen proberen op te tellen, als je over je totaal heen gaat hoef je alle sub-combinaties niet meer te proberen.

[Soultaker]

Meer specifiek is 't een subset sum probleem. Een oplossing kun je vrij efficiënt vinden in pseudo-polyonomiale tijd, maar er kunnen natuurlijk heel veel oplossingen zijn, dus als je die allemaal wil vinden kan dat weer de bottleneck worden.

[Creepy]

creator1988 schreef op maandag 30 juli 2012 @ 19:58:
Ik heb een array met getallen, en een som die ik wil bereiken. Bijvoorbeeld:

[ 10, 10, 10, 10, 10, 10, 10, 50 ]

en de som moet worden: 70.

Mogelijke combinaties zijn daar dan: [ 10, 10, 50 ] en [ 10, 10, 10, 10, 10, 10, 10 ].

Hoe genereer ik die een beetje snel?

En wat heb je zelf al geprobeerd? Wat voor mogelijkheden heb je zelf al gevonden? Nog helemaal niks?

[Matis]

Ik zal eerst alle getallen indexeren, hoevaak komt getal N voor? Daarna gooi je alle getallen weg die groter zijn dan de uitkomst en je limiteerd alle hoeveelheid getallen tot de uitkomst.
Daarna ga je van groot naar klein op zoek naar de grootst mogelijke waarde binnen het restand.

[ID-College]

Ik vraag mij meer af: hoe kom je eraan? Is dit een verzameling van waarden die voor het gemak in een array is gestopt of zit hier een reden achter?

[RayNbow]

creator1988 schreef op maandag 30 juli 2012 @ 19:58:
Ik heb een array met getallen [...]

Wat voor getallen? Integers? Positieve integers? Etc.?

In het geval van positieve integers kun je het zo oplossen, al levert het met bovenstaande voorbeeld wel "dubbele" antwoorden op vanwege het getal 10 dat meerdere keren voorkomt:

Haskell:

f 0 xs = [[]]
f s [] = []
f s (x:xs)
  | x <= s = map (x:) (f (s-x) xs) ++ f s xs
  | otherwise = f s xs

(De versie met de eis van positieve integers was overigens een oude practicumopgave op de TU Delft)

[nielskool]

lol, had een keer een programma gemaakt die alle mogelijke berekeningen deed om te zoeken hoe hij op een bepaald antwoord uit kon komen.
+, -, /, *, ^, wortel en dan was nog in te stellen tot hoe diep de formule mocht gaan.
het programma checkte de formule op een ander set waardes om te kijken of daar de zelfde formule werkte.

[creator1988]

leuk_he schreef op maandag 30 juli 2012 @ 20:13:
HMS is me al voor.

in dit geval:
hoe groot is de array?
Is de ene 10 gelijk aan de andere 10? dan kun je de array verkleinen ([ 5x 10], \[1x50]) en neemt je aantal mogelijkheden af.
array sorteren van groot naar klein, dan en eerst de grote getallen proberen op te tellen, als je over je totaal heen gaat hoef je alle sub-combinaties niet meer te proberen.

n tussen de 0 en 30.

Creepy schreef op maandag 30 juli 2012 @ 23:52:
[...]

En wat heb je zelf al geprobeerd? Wat voor mogelijkheden heb je zelf al gevonden? Nog helemaal niks?

Brute force, powerset bepalen, kijken welke matchet.

ID-College schreef op dinsdag 31 juli 2012 @ 00:46:
Ik vraag mij meer af: hoe kom je eraan? Is dit een verzameling van waarden die voor het gemak in een array is gestopt of zit hier een reden achter?

Spelletje, beperkte set aan kaarten die je in handen hebt. (Positieve integers ja).

Op dit moment brute-force'ing, maar niet echt efficient, zeker niet in gebieden waar thread blocking killing is (hoi node.js!). Ik zal eens gaan experimenteren met de subset sum.

F.y.i. mijn huidige implementatie (brute force in JS):

JavaScript:

        var allCombis = powerset(this.money.filter(function (m) {
            return m > 0;
        }));
                
        var combis = allCombis.filter(function (c) {
            var sum = 0;
            for (var ix = 0; ix < c.length; ix++) {
                sum += c[ix];
            }
            
            return sum === amount
        });
        
        var choseArr = combis.sort(function (c1, c2) {
            return c1.length > c2.length ? 1 : (c1.length === c2.length ? 0 : -1);
        });
        
       var res = choseArr[0];

    function powerset(ary) {
        var ps = [[]];
        for (var i=0; i < ary.length; i++) {
            for (var j = 0, len = ps.length; j < len; j++) {
                ps.push(ps[j].concat(ary[i]));
            }
        }
        return ps;
    }

[RayNbow]

Geen idee of dit efficiente JavaScript code is...

JavaScript:

function f(s, xs) {
    var otherwise = true;
    var prepend = function(y) {return function(ys) {return [y].concat(ys);};};
    
    return (s === 0)          ?  [[]]
         : (xs.length === 0)  ?  []
         : (xs[0] <= s)       ?  f(s-xs[0], xs.slice(1)).map(prepend(xs[0]))
                                 .concat(f(s, xs.slice(1)))
         : otherwise          ?  f(s, xs.slice(1))
         : undefined;
}

Maar serieus, als je weet dat je alleen te maken hebt met positieve getallen in je lijst, dan kun je slim backtracken:

Je begint gewoon bij het eerste element uit je lijst. Nu zijn er twee mogelijkheden:

1. Het element is kleiner dan/gelijk aan de doelsom en kan dus eventueel deel uitmaken van een oplossing. Je hebt nu twee keuzes:
   1. Je laat dit element deel uitmaken van de oplossing en genereert alle oplossingen voor het bijbehorende subprobleem. Bij alle oplossingen van het subprobleem voeg je dit element toe.
   2. Je slaat dit element over en genereert alle oplossingen voor het bijbehorende subprobleem.
2. Het element is groter dan de doelsom en kan niet deel uitmaken van een oplossing. Sla het element over en genereer de oplossingen voor het bijbehorende subprobleem.

Verder geldt:

1. Telkens wanneer je doelsom de 0 bereikt, heb je een oplossing gevonden.
2. Wanneer je geen resterende elementen meer in de lijst hebt staan en nog steeds een doelsom (ongelijk aan 0) hebt, dan is er geen oplossing voor dit (deel)probleem.