Finden aller möglichen Zahlenkombinationen, um eine bestimmte Summe zu erreichen

232

Wie würden Sie alle möglichen Kombinationen von Additionen aus einem bestimmten Satz Nvon Zahlen testen, damit sie sich zu einer bestimmten endgültigen Zahl addieren?

Ein kurzes Beispiel:

  • Satz von Zahlen zum Hinzufügen: N = {1,5,22,15,0,...}
  • Erwünschtes Ergebnis: 12345
James P.
quelle
@ James - Ich denke, dein Problem muss geklärt werden. Wie lauten die Regeln? Können Sie nur beliebige Zahlen auswählen? Welche Zahlen sind im Set? Was sind Ihre Einschränkungen?
jmort253
9
Der Wikipedia-Artikel ( en.wikipedia.org/wiki/Subset_sum_problem ) erwähnt sogar, dass dieses Problem eine gute Einführung in die Klasse der NP-vollständigen Probleme ist.
user57368
1
@ jmort253: Ich glaube, es gibt keine anderen Einschränkungen als eine Reihe von Ganzzahlen, die positiv und niedriger als die als Ziel angegebene Zahl sind. Es kann eine beliebige Zahlenkombination verwendet werden. Es sind keine Hausaufgaben, sondern die Art von Problem, die Sie lösen müssen, wenn Sie sich für einige Jobs bewerben. Normalerweise kann ich mir bei Bedarf einen Algorithmus ausdenken, bin mir aber nicht sicher, wie ich so etwas anzeigen soll. Es muss irgendwie zerlegt werden (rekursiv?).
James P.
3
@ James, Benötigen Sie die Kombinationen oder nur die Anzahl der Teilmengen, die sich zur Summe addieren?
st0le
6
Können wir dasselbe Element des Originalsatzes mehrmals verwenden? Wenn zum Beispiel die Eingabe {1,2,3,5} und Ziel 10 ist, ist 5 + 5 = 10 eine akzeptable Lösung?
Alampada

Antworten:

248

Dieses Problem kann durch eine rekursive Kombination aller möglichen Summen gelöst werden, die diejenigen herausfiltern, die das Ziel erreichen. Hier ist der Algorithmus in Python:

def subset_sum(numbers, target, partial=[]):
    s = sum(partial)

    # check if the partial sum is equals to target
    if s == target: 
        print "sum(%s)=%s" % (partial, target)
    if s >= target:
        return  # if we reach the number why bother to continue

    for i in range(len(numbers)):
        n = numbers[i]
        remaining = numbers[i+1:]
        subset_sum(remaining, target, partial + [n]) 


if __name__ == "__main__":
    subset_sum([3,9,8,4,5,7,10],15)

    #Outputs:
    #sum([3, 8, 4])=15
    #sum([3, 5, 7])=15
    #sum([8, 7])=15
    #sum([5, 10])=15

Diese Art von Algorithmen wird in der folgenden Vorlesung über abstrakte Programmierung von Standford sehr gut erläutert. Dieses Video ist sehr empfehlenswert, um zu verstehen, wie Rekursion funktioniert, um Permutationen von Lösungen zu generieren.

Bearbeiten

Das obige als Generatorfunktion, was es ein bisschen nützlicher macht. Benötigt Python 3.3+ wegen yield from.

def subset_sum(numbers, target, partial=[], partial_sum=0):
    if partial_sum == target:
        yield partial
    if partial_sum >= target:
        return
    for i, n in enumerate(numbers):
        remaining = numbers[i + 1:]
        yield from subset_sum(remaining, target, partial + [n], partial_sum + n)

Hier ist die Java-Version desselben Algorithmus:

package tmp;

import java.util.ArrayList;
import java.util.Arrays;

class SumSet {
    static void sum_up_recursive(ArrayList<Integer> numbers, int target, ArrayList<Integer> partial) {
       int s = 0;
       for (int x: partial) s += x;
       if (s == target)
            System.out.println("sum("+Arrays.toString(partial.toArray())+")="+target);
       if (s >= target)
            return;
       for(int i=0;i<numbers.size();i++) {
             ArrayList<Integer> remaining = new ArrayList<Integer>();
             int n = numbers.get(i);
             for (int j=i+1; j<numbers.size();j++) remaining.add(numbers.get(j));
             ArrayList<Integer> partial_rec = new ArrayList<Integer>(partial);
             partial_rec.add(n);
             sum_up_recursive(remaining,target,partial_rec);
       }
    }
    static void sum_up(ArrayList<Integer> numbers, int target) {
        sum_up_recursive(numbers,target,new ArrayList<Integer>());
    }
    public static void main(String args[]) {
        Integer[] numbers = {3,9,8,4,5,7,10};
        int target = 15;
        sum_up(new ArrayList<Integer>(Arrays.asList(numbers)),target);
    }
}

Es ist genau die gleiche Heuristik. Mein Java ist ein bisschen verrostet, aber ich denke, es ist leicht zu verstehen.

C # -Konvertierung der Java-Lösung: (von @JeremyThompson)

public static void Main(string[] args)
{
    List<int> numbers = new List<int>() { 3, 9, 8, 4, 5, 7, 10 };
    int target = 15;
    sum_up(numbers, target);
}

private static void sum_up(List<int> numbers, int target)
{
    sum_up_recursive(numbers, target, new List<int>());
}

private static void sum_up_recursive(List<int> numbers, int target, List<int> partial)
{
    int s = 0;
    foreach (int x in partial) s += x;

    if (s == target)
        Console.WriteLine("sum(" + string.Join(",", partial.ToArray()) + ")=" + target);

    if (s >= target)
        return;

    for (int i = 0; i < numbers.Count; i++)
    {
        List<int> remaining = new List<int>();
        int n = numbers[i];
        for (int j = i + 1; j < numbers.Count; j++) remaining.Add(numbers[j]);

        List<int> partial_rec = new List<int>(partial);
        partial_rec.Add(n);
        sum_up_recursive(remaining, target, partial_rec);
    }
}

Ruby-Lösung: (von @emaillenin)

def subset_sum(numbers, target, partial=[])
  s = partial.inject 0, :+
# check if the partial sum is equals to target

  puts "sum(#{partial})=#{target}" if s == target

  return if s >= target # if we reach the number why bother to continue

  (0..(numbers.length - 1)).each do |i|
    n = numbers[i]
    remaining = numbers.drop(i+1)
    subset_sum(remaining, target, partial + [n])
  end
end

subset_sum([3,9,8,4,5,7,10],15)

Bearbeiten: Komplexitätsdiskussion

Wie andere erwähnen, ist dies ein NP-hartes Problem . Es kann in der Exponentialzeit O (2 ^ n) gelöst werden, zum Beispiel für n = 10 gibt es 1024 mögliche Lösungen. Wenn sich die Ziele, die Sie erreichen möchten, in einem niedrigen Bereich befinden, funktioniert dieser Algorithmus. Also zum Beispiel:

subset_sum([1,2,3,4,5,6,7,8,9,10],100000) generiert 1024 Zweige, da das Ziel mögliche Lösungen nie herausfiltern kann.

Auf der anderen Seite werden subset_sum([1,2,3,4,5,6,7,8,9,10],10)nur 175 Zweige generiert, da das Ziel zu erreichen ist10 viele Kombinationen herausfiltern kann.

Wenn Nund Targetsind große Zahlen, sollte man in eine ungefähre Version der Lösung übergehen.

Manuel Salvadores
quelle
1
Java-Optimierung: ArrayList <Integer> teilweise_rec = neue ArrayList <Integer> (teilweise); partielle_rec.add (n); Dies macht eine Kopie von teilweise. und addiert somit O (N). Ein besserer Weg ist, einfach "partiell.add (n)" die Rekursion durchzuführen und dann "partiell.entfernen (partielle.Größe -1). Ich überprüfe Ihren Code erneut, um sicherzugehen. Es funktioniert gut
Christian Bongiorno
4
Diese Lösung funktioniert nicht in allen Fällen. Bedenken Sie [1, 2, 0, 6, -3, 3], 3- es wird nur [1,2], [0,3], [3][6, -3, 3]
ausgegeben,
11
Es funktioniert auch nicht für jede Kombination, zum Beispiel [1, 2, 5], 5nur Ausgänge [5], wenn [1, 1, 1, 1, 1], [2, 2, 1]und [2, 1, 1, 1]sind Lösungen.
cbrad
3
@cbrad das liegt an i+1in remaining = numbers[i+1:]. Es sieht so aus, als ob dieser Algorithmus keine Duplikate zulässt.
Leonid Vasilev
1
@cbrad Um auch Lösungen einschließlich Duplikate wie zu [1, 1, 3]erhalten, werfen Sie einen Blick auf stackoverflow.com/a/34971783/3684296 (Python)
Mesa
36

Die Lösung dieses Problems wurde im Internet millionenfach gegeben. Das Problem heißt Das Münzwechselproblem . Lösungen finden Sie unter http://rosettacode.org/wiki/Count_the_coins und ein mathematisches Modell davon unter http://jaqm.ro/issues/volume-5,issue-2/pdfs/patterson_harmel.pdf (oder bei Google Coin Change) Problem ).

Interessant ist übrigens die Scala-Lösung von Tsagadai. In diesem Beispiel wird entweder 1 oder 0 erzeugt. Als Nebeneffekt werden alle möglichen Lösungen auf der Konsole aufgelistet. Es zeigt die Lösung an, macht sie jedoch in keiner Weise verwendbar.

Um so nützlich wie möglich zu sein, sollte der Code a zurückgeben List[List[Int]] , damit die Anzahl der Lösungen (Länge der Liste der Listen), die "beste" Lösung (die kürzeste Liste) oder alle möglichen Lösungen ermittelt werden können.

Hier ist ein Beispiel. Es ist sehr ineffizient, aber leicht zu verstehen.

object Sum extends App {

  def sumCombinations(total: Int, numbers: List[Int]): List[List[Int]] = {

    def add(x: (Int, List[List[Int]]), y: (Int, List[List[Int]])): (Int, List[List[Int]]) = {
      (x._1 + y._1, x._2 ::: y._2)
    }

    def sumCombinations(resultAcc: List[List[Int]], sumAcc: List[Int], total: Int, numbers: List[Int]): (Int, List[List[Int]]) = {
      if (numbers.isEmpty || total < 0) {
        (0, resultAcc)
      } else if (total == 0) {
        (1, sumAcc :: resultAcc)
      } else {
        add(sumCombinations(resultAcc, sumAcc, total, numbers.tail), sumCombinations(resultAcc, numbers.head :: sumAcc, total - numbers.head, numbers))
      }
    }

    sumCombinations(Nil, Nil, total, numbers.sortWith(_ > _))._2
  }

  println(sumCombinations(15, List(1, 2, 5, 10)) mkString "\n")
}

Beim Ausführen wird Folgendes angezeigt:

List(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1)
List(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2)
List(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2)
List(1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2)
List(1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2)
List(1, 1, 1, 1, 1, 2, 2, 2, 2, 2)
List(1, 1, 1, 2, 2, 2, 2, 2, 2)
List(1, 2, 2, 2, 2, 2, 2, 2)
List(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 5)
List(1, 1, 1, 1, 1, 1, 1, 1, 2, 5)
List(1, 1, 1, 1, 1, 1, 2, 2, 5)
List(1, 1, 1, 1, 2, 2, 2, 5)
List(1, 1, 2, 2, 2, 2, 5)
List(2, 2, 2, 2, 2, 5)
List(1, 1, 1, 1, 1, 5, 5)
List(1, 1, 1, 2, 5, 5)
List(1, 2, 2, 5, 5)
List(5, 5, 5)
List(1, 1, 1, 1, 1, 10)
List(1, 1, 1, 2, 10)
List(1, 2, 2, 10)
List(5, 10)

Das sumCombinations() Funktion kann für sich allein verwendet werden, und das Ergebnis kann weiter analysiert werden, um die "beste" Lösung (die kürzeste Liste) oder die Anzahl der Lösungen (die Anzahl der Listen) anzuzeigen.

Beachten Sie, dass die Anforderungen auch dann möglicherweise nicht vollständig erfüllt sind. Es kann vorkommen, dass die Reihenfolge jeder Liste in der Lösung von Bedeutung ist. In einem solchen Fall müsste jede Liste so oft dupliziert werden, wie es eine Kombination ihrer Elemente gibt. Oder wir interessieren uns nur für die Kombinationen, die unterschiedlich sind.

Zum Beispiel könnten wir in Betracht ziehen, List(5, 10)dass dies zwei Kombinationen ergeben sollte: List(5, 10)und List(10, 5). Denn List(5, 5, 5)je nach Anforderung können drei oder nur eine Kombination angegeben werden. Für ganze Zahlen sind die drei Permutationen äquivalent, aber wenn es sich um Münzen handelt, wie im "Münzwechselproblem", sind sie es nicht.

Ebenfalls nicht in den Anforderungen angegeben ist die Frage, ob jede Zahl (oder Münze) nur einmal oder mehrmals verwendet werden darf. Wir könnten (und sollten!) Das Problem auf eine Liste von Vorkommenslisten jeder Zahl verallgemeinern. Dies führt im wirklichen Leben dazu, dass "mit einem Satz Münzen (und nicht mit einem Satz Münzwerte) ein bestimmter Geldbetrag verdient werden kann". Das ursprüngliche Problem ist nur ein besonderer Fall in diesem Fall, in dem jede Münze so oft vorkommt, wie erforderlich ist, um den Gesamtbetrag mit jedem einzelnen Münzwert zu ermitteln.

Pierre-Yves Saumont
quelle
14
Dieses Problem ist nicht genau das gleiche wie das Münzwechselproblem. OP fordert alle Kombinationen, nicht nur die minimalen. Und vermutlich können die ganzen Zahlen in der Menge negativ sein. Daher sind bestimmte Optimierungen des Münzwechselproblems mit diesem Problem nicht möglich.
Thomas McLeod
5
und auch dieses Problem erlaubt die Wiederholung von Gegenständen, ich bin nicht sicher, ob OP dies wollte, sondern eher ein Rucksackproblem
caub
34

Im Haskell :

filter ((==) 12345 . sum) $ subsequences [1,5,22,15,0,..]

Und J :

(]#~12345=+/@>)(]<@#~[:#:@i.2^#)1 5 22 15 0 ...

Wie Sie vielleicht bemerken, verfolgen beide den gleichen Ansatz und teilen das Problem in zwei Teile: Generieren Sie jedes Mitglied des Potenzsatzes und überprüfen Sie die Summe jedes Mitglieds zum Ziel.

Es gibt andere Lösungen, aber dies ist die einfachste.

Benötigen Sie Hilfe bei einem oder bei der Suche nach einem anderen Ansatz?

kurzlebig
quelle
3
Wow, das ist ein ziemlich prägnanter Code. Mir geht es gut mit deiner Antwort. Ich denke, ich muss mich nur ein wenig über Algorithmen im Allgemeinen informieren. Ich werde einen Blick auf die Syntax der beiden Sprachen werfen, da Sie meine Neugier geweckt haben.
James P.
Ich habe gerade Haskell installiert, um dies auszuprobieren. Kann ich es definitiv nicht einfach einfügen und ausführen lassen, not in scope: 'subsequences'irgendwelche Zeiger?
Hart CO
4
@ HartCO ein bisschen spät zur Party, aberimport Data.List
Jir
28

Eine Javascript-Version:

function subsetSum(numbers, target, partial) {
  var s, n, remaining;

  partial = partial || [];

  // sum partial
  s = partial.reduce(function (a, b) {
    return a + b;
  }, 0);

  // check if the partial sum is equals to target
  if (s === target) {
    console.log("%s=%s", partial.join("+"), target)
  }

  if (s >= target) {
    return;  // if we reach the number why bother to continue
  }

  for (var i = 0; i < numbers.length; i++) {
    n = numbers[i];
    remaining = numbers.slice(i + 1);
    subsetSum(remaining, target, partial.concat([n]));
  }
}

subsetSum([3,9,8,4,5,7,10],15);

// output:
// 3+8+4=15
// 3+5+7=15
// 8+7=15
// 5+10=15

rbarilani
quelle
Der Code hat einen Fehler in der Scheibe, sollte remaining = numbers.slice(); remaining.slice(i + 1);sonst numbers.slice(i + 1);das Zahlenarray
ändern
@Emeeus, ich glaube nicht, dass das stimmt. sliceGibt eine (flache) Kopie zurück, das numbersArray wird nicht geändert .
Dario Seidl
@DarioSeidl Ja, Slice gibt eine Kopie zurück. Es ändert das Array nicht. Das ist der Punkt. Wenn Sie es nicht einer Variablen zuweisen, ändern Sie es nicht. In diesem Fall müssen wir meines Wissens eine modifizierte Version übergeben, nicht das Original. Siehe diese jsfiddle.net/che06t3w/1
Emeeus
1
@Redu ... zum Beispiel ist eine einfache Möglichkeit, den Algorithmus leicht zu modifizieren und eine innere Funktion zu verwenden: jsbin.com/lecokaw/edit?js,console
rbarilani
1
Der angegebene Code erhält nicht unbedingt alle Kombinationen. Wenn Sie beispielsweise [1,2] setzen, gibt 3 nur 1 + 2 = 3 zurück, nicht 1 + 1 + 1 oder 2 + 1
JuicY_Burrito
12

C ++ - Version desselben Algorithmus

#include <iostream>
#include <list>
void subset_sum_recursive(std::list<int> numbers, int target, std::list<int> partial)
{
        int s = 0;
        for (std::list<int>::const_iterator cit = partial.begin(); cit != partial.end(); cit++)
        {
            s += *cit;
        }
        if(s == target)
        {
                std::cout << "sum([";

                for (std::list<int>::const_iterator cit = partial.begin(); cit != partial.end(); cit++)
                {
                    std::cout << *cit << ",";
                }
                std::cout << "])=" << target << std::endl;
        }
        if(s >= target)
            return;
        int n;
        for (std::list<int>::const_iterator ai = numbers.begin(); ai != numbers.end(); ai++)
        {
            n = *ai;
            std::list<int> remaining;
            for(std::list<int>::const_iterator aj = ai; aj != numbers.end(); aj++)
            {
                if(aj == ai)continue;
                remaining.push_back(*aj);
            }
            std::list<int> partial_rec=partial;
            partial_rec.push_back(n);
            subset_sum_recursive(remaining,target,partial_rec);

        }
}

void subset_sum(std::list<int> numbers,int target)
{
    subset_sum_recursive(numbers,target,std::list<int>());
}
int main()
{
    std::list<int> a;
    a.push_back (3); a.push_back (9); a.push_back (8);
    a.push_back (4);
    a.push_back (5);
    a.push_back (7);
    a.push_back (10);
    int n = 15;
    //std::cin >> n;
    subset_sum(a, n);
    return 0;
}
smac89
quelle
11

C # -Version der @ msalvadores-Code-Antwort

void Main()
{
    int[] numbers = {3,9,8,4,5,7,10};
    int target = 15;
    sum_up(new List<int>(numbers.ToList()),target);
}

static void sum_up_recursive(List<int> numbers, int target, List<int> part)
{
   int s = 0;
   foreach (int x in part)
   {
       s += x;
   }
   if (s == target)
   {
        Console.WriteLine("sum(" + string.Join(",", part.Select(n => n.ToString()).ToArray()) + ")=" + target);
   }
   if (s >= target)
   {
        return;
   }
   for (int i = 0;i < numbers.Count;i++)
   {
         var remaining = new List<int>();
         int n = numbers[i];
         for (int j = i + 1; j < numbers.Count;j++)
         {
             remaining.Add(numbers[j]);
         }
         var part_rec = new List<int>(part);
         part_rec.Add(n);
         sum_up_recursive(remaining,target,part_rec);
   }
}
static void sum_up(List<int> numbers, int target)
{
    sum_up_recursive(numbers,target,new List<int>());
}
smac89
quelle
4

Ich dachte, ich würde eine Antwort auf diese Frage verwenden, konnte es aber nicht. Hier ist meine Antwort. Es wird eine modifizierte Version einer Antwort in Struktur und Interpretation von Computerprogrammen verwendet . Ich denke, dies ist eine bessere rekursive Lösung und sollte den Puristen mehr gefallen.

Meine Antwort ist in Scala (und ich entschuldige mich, wenn meine Scala scheiße ist, ich habe gerade angefangen, sie zu lernen). Die Verrücktheit von findSumCombinations besteht darin, die ursprüngliche Liste für die Rekursion zu sortieren und eindeutig zu machen, um Dupes zu verhindern.

def findSumCombinations(target: Int, numbers: List[Int]): Int = {
  cc(target, numbers.distinct.sortWith(_ < _), List())
}

def cc(target: Int, numbers: List[Int], solution: List[Int]): Int = {
  if (target == 0) {println(solution); 1 }
  else if (target < 0 || numbers.length == 0) 0
  else 
    cc(target, numbers.tail, solution) 
    + cc(target - numbers.head, numbers, numbers.head :: solution)
}

Um es zu benutzen:

 > findSumCombinations(12345, List(1,5,22,15,0,..))
 * Prints a whole heap of lists that will sum to the target *
Tsagadai
quelle
4
Thank you.. ephemient

Ich habe oben Logik von Python zu PHP konvertiert.

<?php
$data = array(array(2,3,5,10,15),array(4,6,23,15,12),array(23,34,12,1,5));
$maxsum = 25;

print_r(bestsum($data,$maxsum));  //function call

function bestsum($data,$maxsum)
{
$res = array_fill(0, $maxsum + 1, '0');
$res[0] = array();              //base case
foreach($data as $group)
{
 $new_res = $res;               //copy res

  foreach($group as $ele)
  {
    for($i=0;$i<($maxsum-$ele+1);$i++)
    {   
        if($res[$i] != 0)
        {
            $ele_index = $i+$ele;
            $new_res[$ele_index] = $res[$i];
            $new_res[$ele_index][] = $ele;
        }
    }
  }

  $res = $new_res;
}

 for($i=$maxsum;$i>0;$i--)
  {
    if($res[$i]!=0)
    {
        return $res[$i];
        break;
    }
  }
return array();
}
?>
bala
quelle
4

Eine andere Python-Lösung wäre, das itertools.combinationsModul wie folgt zu verwenden:

#!/usr/local/bin/python

from itertools import combinations

def find_sum_in_list(numbers, target):
    results = []
    for x in range(len(numbers)):
        results.extend(
            [   
                combo for combo in combinations(numbers ,x)  
                    if sum(combo) == target
            ]   
        )   

    print results

if __name__ == "__main__":
    find_sum_in_list([3,9,8,4,5,7,10], 15)

Ausgabe: [(8, 7), (5, 10), (3, 8, 4), (3, 5, 7)]

Brainasium
quelle
es funktioniert nicht zB: find_sum_in_list (Bereich (0,8), 4). Gefunden: [(4,), (0, 4), (1, 3), (0, 1, 3)]. Aber (2, 2) ist auch eine Option!
Andre Araujo
@AndreAraujo: Es macht keinen Sinn, 0 zu verwenden, aber wenn Sie (1,8) verwenden, funktioniert itertools.combinations_with_replacement und gibt auch 2,2 aus.
Rubenisme
@ Rubenisme Ja, Mann! Das Problem war der Ersatz! Vielen Dank! ;-)
Andre Araujo
4

Hier ist eine Lösung in R.

subset_sum = function(numbers,target,partial=0){
  if(any(is.na(partial))) return()
  s = sum(partial)
  if(s == target) print(sprintf("sum(%s)=%s",paste(partial[-1],collapse="+"),target))
  if(s > target) return()
  for( i in seq_along(numbers)){
    n = numbers[i]
    remaining = numbers[(i+1):length(numbers)]
    subset_sum(remaining,target,c(partial,n))
  }
}
Kennzeichen
quelle
Ich suche nach einer Lösung in R, aber diese funktioniert bei mir nicht. Gibt zum Beispiel subset_sum(numbers = c(1:2), target = 5)zurück "sum(1+2+2)=5". Die Kombination 1 + 1 + 1 + 1 + 1 fehlt jedoch. Beim Setzen von Zielen auf höhere Zahlen (z. B. 20) fehlen noch mehr Kombinationen.
Frederick
Was Sie beschreiben, ist nicht das, was die Funktion zurückgeben soll. Schauen Sie sich die akzeptierte Antwort an. Die Tatsache, dass 2 zweimal wiederholt wird, ist ein Artefakt dafür, wie R Reihen erzeugt und Teilmengen bildet, nicht beabsichtigtes Verhalten.
Mark
subset_sum(1:2, 4)sollte keine Lösungen zurückgeben, da es keine Kombination von 1 und 2 gibt, die zu 4 addiert. Was zu meiner Funktion hinzugefügt werden muss, ist ein Escape, wenn ies größer als die Länge vonnumbers
Mark
3

Hier ist eine Java-Version, die sich gut für kleine N und sehr große Zielsummen eignet, wenn die Komplexität O(t*N)(die dynamische Lösung) größer ist als der Exponentialalgorithmus. Meine Version verwendet ein Meet-in-the-Middle-Attacke sowie ein wenig Shifting, um die Komplexität von klassisch naiv O(n*2^n)auf klassisch zu reduzierenO(2^(n/2)) .

Wenn Sie dies für Sätze mit 32 bis 64 Elementen verwenden möchten, sollten Sie intdie aktuelle Teilmenge in der Schrittfunktion in a ändern , longobwohl die Leistung mit zunehmender Satzgröße offensichtlich drastisch abnimmt. Wenn Sie dies für eine Menge mit einer ungeraden Anzahl von Elementen verwenden möchten, sollten Sie der Menge eine 0 hinzufügen, um sie gerade zu nummerieren.

import java.util.ArrayList;
import java.util.List;

public class SubsetSumMiddleAttack {
    static final int target = 100000000;
    static final int[] set = new int[]{ ... };

    static List<Subset> evens = new ArrayList<>();
    static List<Subset> odds = new ArrayList<>();

    static int[][] split(int[] superSet) {
        int[][] ret = new int[2][superSet.length / 2]; 

        for (int i = 0; i < superSet.length; i++) ret[i % 2][i / 2] = superSet[i];

        return ret;
    }

    static void step(int[] superSet, List<Subset> accumulator, int subset, int sum, int counter) {
        accumulator.add(new Subset(subset, sum));
        if (counter != superSet.length) {
            step(superSet, accumulator, subset + (1 << counter), sum + superSet[counter], counter + 1);
            step(superSet, accumulator, subset, sum, counter + 1);
        }
    }

    static void printSubset(Subset e, Subset o) {
        String ret = "";
        for (int i = 0; i < 32; i++) {
            if (i % 2 == 0) {
                if ((1 & (e.subset >> (i / 2))) == 1) ret += " + " + set[i];
            }
            else {
                if ((1 & (o.subset >> (i / 2))) == 1) ret += " + " + set[i];
            }
        }
        if (ret.startsWith(" ")) ret = ret.substring(3) + " = " + (e.sum + o.sum);
        System.out.println(ret);
    }

    public static void main(String[] args) {
        int[][] superSets = split(set);

        step(superSets[0], evens, 0,0,0);
        step(superSets[1], odds, 0,0,0);

        for (Subset e : evens) {
            for (Subset o : odds) {
                if (e.sum + o.sum == target) printSubset(e, o);
            }
        }
    }
}

class Subset {
    int subset;
    int sum;

    Subset(int subset, int sum) {
        this.subset = subset;
        this.sum = sum;
    }
}
jimpudar
quelle
3

Dies ähnelt einem Münzwechselproblem

public class CoinCount 
{   
public static void main(String[] args)
{
    int[] coins={1,4,6,2,3,5};
    int count=0;

    for (int i=0;i<coins.length;i++)
    {
        count=count+Count(9,coins,i,0);
    }
    System.out.println(count);
}

public static int Count(int Sum,int[] coins,int index,int curSum)
{
    int count=0;

    if (index>=coins.length)
        return 0;

    int sumNow=curSum+coins[index];
    if (sumNow>Sum)
        return 0;
    if (sumNow==Sum)
        return 1;

    for (int i= index+1;i<coins.length;i++)
        count+=Count(Sum,coins,i,sumNow);

    return count;       
}
}
DJ '
quelle
2

Sehr effizienter Algorithmus mit Tabellen, die ich vor ein paar Jahren in C ++ geschrieben habe.

Wenn Sie DRUCKEN 1 einstellen, werden alle Kombinationen gedruckt (es wird jedoch nicht die effiziente Methode verwendet).

Es ist so effizient, dass es mehr als 10 ^ 14 Kombinationen in weniger als 10 ms berechnet.

#include <stdio.h>
#include <stdlib.h>
//#include "CTime.h"

#define SUM 300
#define MAXNUMsSIZE 30

#define PRINT 0


long long CountAddToSum(int,int[],int,const int[],int);
void printr(const int[], int);
long long table1[SUM][MAXNUMsSIZE];

int main()
{
    int Nums[]={3,4,5,6,7,9,13,11,12,13,22,35,17,14,18,23,33,54};
    int sum=SUM;
    int size=sizeof(Nums)/sizeof(int);
    int i,j,a[]={0};
    long long N=0;
    //CTime timer1;

    for(i=0;i<SUM;++i) 
        for(j=0;j<MAXNUMsSIZE;++j) 
            table1[i][j]=-1;

    N = CountAddToSum(sum,Nums,size,a,0); //algorithm
    //timer1.Get_Passd();

    //printf("\nN=%lld time=%.1f ms\n", N,timer1.Get_Passd());
    printf("\nN=%lld \n", N);
    getchar();
    return 1;
}

long long CountAddToSum(int s, int arr[],int arrsize, const int r[],int rsize)
{
    static int totalmem=0, maxmem=0;
    int i,*rnew;
    long long result1=0,result2=0;

    if(s<0) return 0;
    if (table1[s][arrsize]>0 && PRINT==0) return table1[s][arrsize];
    if(s==0)
    {
        if(PRINT) printr(r, rsize);
        return 1;
    }
    if(arrsize==0) return 0;

    //else
    rnew=(int*)malloc((rsize+1)*sizeof(int));

    for(i=0;i<rsize;++i) rnew[i]=r[i]; 
    rnew[rsize]=arr[arrsize-1];

    result1 =  CountAddToSum(s,arr,arrsize-1,rnew,rsize);
    result2 =  CountAddToSum(s-arr[arrsize-1],arr,arrsize,rnew,rsize+1);
    table1[s][arrsize]=result1+result2;
    free(rnew);

    return result1+result2;

}

void printr(const int r[], int rsize)
{
    int lastr=r[0],count=0,i;
    for(i=0; i<rsize;++i) 
    {
        if(r[i]==lastr)
            count++;
        else
        {
            printf(" %d*%d ",count,lastr);
            lastr=r[i];
            count=1;
        }
    }
    if(r[i-1]==lastr) printf(" %d*%d ",count,lastr);

    printf("\n");

}
Mendi Barel
quelle
Hallo! Ich brauche einen Code, um so etwas zu tun. Finde alle möglichen Summen von Sätzen mit 6 Zahlen in einer Liste mit 60 Zahlen. Die Summen sollten im Bereich von min 180, max 191 liegen. Könnte dieser Code dafür angepasst werden? Wo kann dieser Code in der Cloud ausgeführt werden? Ich versuchte es ohne Erfolg bei Codenvy
Defreturn
2

Excel VBA-Version unten. Ich musste dies in VBA implementieren (nicht meine Präferenz, beurteilen Sie mich nicht!) Und verwendete die Antworten auf dieser Seite für den Ansatz. Ich lade hoch, falls andere auch eine VBA-Version benötigen.

Option Explicit

Public Sub SumTarget()
    Dim numbers(0 To 6)  As Long
    Dim target As Long

    target = 15
    numbers(0) = 3: numbers(1) = 9: numbers(2) = 8: numbers(3) = 4: numbers(4) = 5
    numbers(5) = 7: numbers(6) = 10

    Call SumUpTarget(numbers, target)
End Sub

Public Sub SumUpTarget(numbers() As Long, target As Long)
    Dim part() As Long
    Call SumUpRecursive(numbers, target, part)
End Sub

Private Sub SumUpRecursive(numbers() As Long, target As Long, part() As Long)

    Dim s As Long, i As Long, j As Long, num As Long
    Dim remaining() As Long, partRec() As Long
    s = SumArray(part)

    If s = target Then Debug.Print "SUM ( " & ArrayToString(part) & " ) = " & target
    If s >= target Then Exit Sub

    If (Not Not numbers) <> 0 Then
        For i = 0 To UBound(numbers)
            Erase remaining()
            num = numbers(i)
            For j = i + 1 To UBound(numbers)
                AddToArray remaining, numbers(j)
            Next j
            Erase partRec()
            CopyArray partRec, part
            AddToArray partRec, num
            SumUpRecursive remaining, target, partRec
        Next i
    End If

End Sub

Private Function ArrayToString(x() As Long) As String
    Dim n As Long, result As String
    result = "{" & x(n)
    For n = LBound(x) + 1 To UBound(x)
        result = result & "," & x(n)
    Next n
    result = result & "}"
    ArrayToString = result
End Function

Private Function SumArray(x() As Long) As Long
    Dim n As Long
    SumArray = 0
    If (Not Not x) <> 0 Then
        For n = LBound(x) To UBound(x)
            SumArray = SumArray + x(n)
        Next n
    End If
End Function

Private Sub AddToArray(arr() As Long, x As Long)
    If (Not Not arr) <> 0 Then
        ReDim Preserve arr(0 To UBound(arr) + 1)
    Else
        ReDim Preserve arr(0 To 0)
    End If
    arr(UBound(arr)) = x
End Sub

Private Sub CopyArray(destination() As Long, source() As Long)
    Dim n As Long
    If (Not Not source) <> 0 Then
        For n = 0 To UBound(source)
                AddToArray destination, source(n)
        Next n
    End If
End Sub

Die Ausgabe (in das Direktfenster geschrieben) sollte sein:

SUM ( {3,8,4} ) = 15
SUM ( {3,5,7} ) = 15
SUM ( {8,7} ) = 15
SUM ( {5,10} ) = 15 
CodingQuant
quelle
2

Hier ist eine bessere Version mit besserer Ausgabeformatierung und C ++ 11-Funktionen:

void subset_sum_rec(std::vector<int> & nums, const int & target, std::vector<int> & partialNums) 
{
    int currentSum = std::accumulate(partialNums.begin(), partialNums.end(), 0);
    if (currentSum > target)
        return;
    if (currentSum == target) 
    {
        std::cout << "sum([";
        for (auto it = partialNums.begin(); it != std::prev(partialNums.end()); ++it)
            cout << *it << ",";
        cout << *std::prev(partialNums.end());
        std::cout << "])=" << target << std::endl;
    }
    for (auto it = nums.begin(); it != nums.end(); ++it) 
    {
        std::vector<int> remaining;
        for (auto it2 = std::next(it); it2 != nums.end(); ++it2)
            remaining.push_back(*it2);

        std::vector<int> partial = partialNums;
        partial.push_back(*it);
        subset_sum_rec(remaining, target, partial);
    }
}
Andrushenko Alexander
quelle
2

Nicht rekursive Java -Version, die einfach immer wieder Elemente hinzufügt und diese auf mögliche Werte verteilt. 0werden ignoriert und funktionieren für feste Listen (was Sie erhalten, ist das, womit Sie spielen können) oder eine Liste wiederholbarer Zahlen.

import java.util.*;

public class TestCombinations {

    public static void main(String[] args) {
        ArrayList<Integer> numbers = new ArrayList<>(Arrays.asList(0, 1, 2, 2, 5, 10, 20));
        LinkedHashSet<Integer> targets = new LinkedHashSet<Integer>() {{
            add(4);
            add(10);
            add(25);
        }};

        System.out.println("## each element can appear as many times as needed");
        for (Integer target: targets) {
            Combinations combinations = new Combinations(numbers, target, true);
            combinations.calculateCombinations();
            for (String solution: combinations.getCombinations()) {
                System.out.println(solution);
            }
        }

        System.out.println("## each element can appear only once");
        for (Integer target: targets) {
            Combinations combinations = new Combinations(numbers, target, false);
            combinations.calculateCombinations();
            for (String solution: combinations.getCombinations()) {
                System.out.println(solution);
            }
        }
    }

    public static class Combinations {
        private boolean allowRepetitions;
        private int[] repetitions;
        private ArrayList<Integer> numbers;
        private Integer target;
        private Integer sum;
        private boolean hasNext;
        private Set<String> combinations;

        /**
         * Constructor.
         *
         * @param numbers Numbers that can be used to calculate the sum.
         * @param target  Target value for sum.
         */
        public Combinations(ArrayList<Integer> numbers, Integer target) {
            this(numbers, target, true);
        }

        /**
         * Constructor.
         *
         * @param numbers Numbers that can be used to calculate the sum.
         * @param target  Target value for sum.
         */
        public Combinations(ArrayList<Integer> numbers, Integer target, boolean allowRepetitions) {
            this.allowRepetitions = allowRepetitions;
            if (this.allowRepetitions) {
                Set<Integer> numbersSet = new HashSet<>(numbers);
                this.numbers = new ArrayList<>(numbersSet);
            } else {
                this.numbers = numbers;
            }
            this.numbers.removeAll(Arrays.asList(0));
            Collections.sort(this.numbers);

            this.target = target;
            this.repetitions = new int[this.numbers.size()];
            this.combinations = new LinkedHashSet<>();

            this.sum = 0;
            if (this.repetitions.length > 0)
                this.hasNext = true;
            else
                this.hasNext = false;
        }

        /**
         * Calculate and return the sum of the current combination.
         *
         * @return The sum.
         */
        private Integer calculateSum() {
            this.sum = 0;
            for (int i = 0; i < repetitions.length; ++i) {
                this.sum += repetitions[i] * numbers.get(i);
            }
            return this.sum;
        }

        /**
         * Redistribute picks when only one of each number is allowed in the sum.
         */
        private void redistribute() {
            for (int i = 1; i < this.repetitions.length; ++i) {
                if (this.repetitions[i - 1] > 1) {
                    this.repetitions[i - 1] = 0;
                    this.repetitions[i] += 1;
                }
            }
            if (this.repetitions[this.repetitions.length - 1] > 1)
                this.repetitions[this.repetitions.length - 1] = 0;
        }

        /**
         * Get the sum of the next combination. When 0 is returned, there's no other combinations to check.
         *
         * @return The sum.
         */
        private Integer next() {
            if (this.hasNext && this.repetitions.length > 0) {
                this.repetitions[0] += 1;
                if (!this.allowRepetitions)
                    this.redistribute();
                this.calculateSum();

                for (int i = 0; i < this.repetitions.length && this.sum != 0; ++i) {
                    if (this.sum > this.target) {
                        this.repetitions[i] = 0;
                        if (i + 1 < this.repetitions.length) {
                            this.repetitions[i + 1] += 1;
                            if (!this.allowRepetitions)
                                this.redistribute();
                        }
                        this.calculateSum();
                    }
                }

                if (this.sum.compareTo(0) == 0)
                    this.hasNext = false;
            }
            return this.sum;
        }

        /**
         * Calculate all combinations whose sum equals target.
         */
        public void calculateCombinations() {
            while (this.hasNext) {
                if (this.next().compareTo(target) == 0)
                    this.combinations.add(this.toString());
            }
        }

        /**
         * Return all combinations whose sum equals target.
         *
         * @return Combinations as a set of strings.
         */
        public Set<String> getCombinations() {
            return this.combinations;
        }

        @Override
        public String toString() {
            StringBuilder stringBuilder = new StringBuilder("" + sum + ": ");
            for (int i = 0; i < repetitions.length; ++i) {
                for (int j = 0; j < repetitions[i]; ++j) {
                    stringBuilder.append(numbers.get(i) + " ");
                }
            }
            return stringBuilder.toString();
        }
    }
}

Beispieleingabe:

numbers: 0, 1, 2, 2, 5, 10, 20
targets: 4, 10, 25

Beispielausgabe:

## each element can appear as many times as needed
4: 1 1 1 1 
4: 1 1 2 
4: 2 2 
10: 1 1 1 1 1 1 1 1 1 1 
10: 1 1 1 1 1 1 1 1 2 
10: 1 1 1 1 1 1 2 2 
10: 1 1 1 1 2 2 2 
10: 1 1 2 2 2 2 
10: 2 2 2 2 2 
10: 1 1 1 1 1 5 
10: 1 1 1 2 5 
10: 1 2 2 5 
10: 5 5 
10: 10 
25: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
25: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 
25: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 
25: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 
25: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 
25: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 
25: 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 
25: 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 
25: 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 
25: 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 
25: 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 
25: 1 1 1 2 2 2 2 2 2 2 2 2 2 2 
25: 1 2 2 2 2 2 2 2 2 2 2 2 2 
25: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 5 
25: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 5 
25: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 5 
25: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 5 
25: 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 5 
25: 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 5 
25: 1 1 1 1 1 1 1 1 2 2 2 2 2 2 5 
25: 1 1 1 1 1 1 2 2 2 2 2 2 2 5 
25: 1 1 1 1 2 2 2 2 2 2 2 2 5 
25: 1 1 2 2 2 2 2 2 2 2 2 5 
25: 2 2 2 2 2 2 2 2 2 2 5 
25: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 5 5 
25: 1 1 1 1 1 1 1 1 1 1 1 1 1 2 5 5 
25: 1 1 1 1 1 1 1 1 1 1 1 2 2 5 5 
25: 1 1 1 1 1 1 1 1 1 2 2 2 5 5 
25: 1 1 1 1 1 1 1 2 2 2 2 5 5 
25: 1 1 1 1 1 2 2 2 2 2 5 5 
25: 1 1 1 2 2 2 2 2 2 5 5 
25: 1 2 2 2 2 2 2 2 5 5 
25: 1 1 1 1 1 1 1 1 1 1 5 5 5 
25: 1 1 1 1 1 1 1 1 2 5 5 5 
25: 1 1 1 1 1 1 2 2 5 5 5 
25: 1 1 1 1 2 2 2 5 5 5 
25: 1 1 2 2 2 2 5 5 5 
25: 2 2 2 2 2 5 5 5 
25: 1 1 1 1 1 5 5 5 5 
25: 1 1 1 2 5 5 5 5 
25: 1 2 2 5 5 5 5 
25: 5 5 5 5 5 
25: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 10 
25: 1 1 1 1 1 1 1 1 1 1 1 1 1 2 10 
25: 1 1 1 1 1 1 1 1 1 1 1 2 2 10 
25: 1 1 1 1 1 1 1 1 1 2 2 2 10 
25: 1 1 1 1 1 1 1 2 2 2 2 10 
25: 1 1 1 1 1 2 2 2 2 2 10 
25: 1 1 1 2 2 2 2 2 2 10 
25: 1 2 2 2 2 2 2 2 10 
25: 1 1 1 1 1 1 1 1 1 1 5 10 
25: 1 1 1 1 1 1 1 1 2 5 10 
25: 1 1 1 1 1 1 2 2 5 10 
25: 1 1 1 1 2 2 2 5 10 
25: 1 1 2 2 2 2 5 10 
25: 2 2 2 2 2 5 10 
25: 1 1 1 1 1 5 5 10 
25: 1 1 1 2 5 5 10 
25: 1 2 2 5 5 10 
25: 5 5 5 10 
25: 1 1 1 1 1 10 10 
25: 1 1 1 2 10 10 
25: 1 2 2 10 10 
25: 5 10 10 
25: 1 1 1 1 1 20 
25: 1 1 1 2 20 
25: 1 2 2 20 
25: 5 20 
## each element can appear only once
4: 2 2 
10: 1 2 2 5 
10: 10 
25: 1 2 2 20 
25: 5 20
Bernat
quelle
1

Um die Kombinationen mit Excel zu finden - (es ist ziemlich einfach). (Ihr Computer darf nicht zu langsam sein)

  1. Gehen Sie zu dieser Seite
  2. Gehen Sie zur Seite "Summe zum Ziel"
  3. Laden Sie die Excel-Datei "Sum to Target" herunter.

    Folgen Sie den Anweisungen auf der Website-Seite.

hoffe das hilft.

Mark van Zoest
quelle
1

Swift 3-Konvertierung der Java-Lösung: (von @JeremyThompson)

protocol _IntType { }
extension Int: _IntType {}


extension Array where Element: _IntType {

    func subsets(to: Int) -> [[Element]]? {

        func sum_up_recursive(_ numbers: [Element], _ target: Int, _ partial: [Element], _ solution: inout [[Element]]) {

            var sum: Int = 0
            for x in partial {
                sum += x as! Int
            }

            if sum == target {
                solution.append(partial)
            }

            guard sum < target else {
                return
            }

            for i in stride(from: 0, to: numbers.count, by: 1) {

                var remaining = [Element]()

                for j in stride(from: i + 1, to: numbers.count, by: 1) {
                    remaining.append(numbers[j])
                }

                var partial_rec = [Element](partial)
                partial_rec.append(numbers[i])

                sum_up_recursive(remaining, target, partial_rec, &solution)
            }
        }

        var solutions = [[Element]]()
        sum_up_recursive(self, to, [Element](), &solutions)

        return solutions.count > 0 ? solutions : nil
    }

}

Verwendung:

let numbers = [3, 9, 8, 4, 5, 7, 10]

if let solution = numbers.subsets(to: 15) {
    print(solution) // output: [[3, 8, 4], [3, 5, 7], [8, 7], [5, 10]]
} else {
    print("not possible")
}
RolandasR
quelle
1

Hiermit können auch alle Antworten gedruckt werden

public void recur(int[] a, int n, int sum, int[] ans, int ind) {
    if (n < 0 && sum != 0)
        return;
    if (n < 0 && sum == 0) {
        print(ans, ind);
        return;
    }
    if (sum >= a[n]) {
        ans[ind] = a[n];
        recur(a, n - 1, sum - a[n], ans, ind + 1);
    }
    recur(a, n - 1, sum, ans, ind);
}

public void print(int[] a, int n) {
    for (int i = 0; i < n; i++)
        System.out.print(a[i] + " ");
    System.out.println();
}

Die Zeitkomplexität ist exponentiell. Reihenfolge von 2 ^ n

Astha Gupta
quelle
1

Ich habe etwas Ähnliches für eine Scala-Aufgabe gemacht. Ich wollte meine Lösung hier veröffentlichen:

 def countChange(money: Int, coins: List[Int]): Int = {
      def getCount(money: Int, remainingCoins: List[Int]): Int = {
        if(money == 0 ) 1
        else if(money < 0 || remainingCoins.isEmpty) 0
        else
          getCount(money, remainingCoins.tail) +
            getCount(money - remainingCoins.head, remainingCoins)
      }
      if(money == 0 || coins.isEmpty) 0
      else getCount(money, coins)
    }
Prabodh Mhalgi
quelle
1

Ich habe das C # -Beispiel auf Objective-c portiert und es in den Antworten nicht gesehen:

//Usage
NSMutableArray* numberList = [[NSMutableArray alloc] init];
NSMutableArray* partial = [[NSMutableArray alloc] init];
int target = 16;
for( int i = 1; i<target; i++ )
{ [numberList addObject:@(i)]; }
[self findSums:numberList target:target part:partial];


//*******************************************************************
// Finds combinations of numbers that add up to target recursively
//*******************************************************************
-(void)findSums:(NSMutableArray*)numbers target:(int)target part:(NSMutableArray*)partial
{
    int s = 0;
    for (NSNumber* x in partial)
    { s += [x intValue]; }

    if (s == target)
    { NSLog(@"Sum[%@]", partial); }

    if (s >= target)
    { return; }

    for (int i = 0;i < [numbers count];i++ )
    {
        int n = [numbers[i] intValue];
        NSMutableArray* remaining = [[NSMutableArray alloc] init];
        for (int j = i + 1; j < [numbers count];j++)
        { [remaining addObject:@([numbers[j] intValue])]; }

        NSMutableArray* partRec = [[NSMutableArray alloc] initWithArray:partial];
        [partRec addObject:@(n)];
        [self findSums:remaining target:target part:partRec];
    }
}
JMan Mousey
quelle
1

@ KeithBellers Antwort mit leicht geänderten Variablennamen und einigen Kommentaren.

    public static void Main(string[] args)
    {
        List<int> input = new List<int>() { 3, 9, 8, 4, 5, 7, 10 };
        int targetSum = 15;
        SumUp(input, targetSum);
    }

    public static void SumUp(List<int> input, int targetSum)
    {
        SumUpRecursive(input, targetSum, new List<int>());
    }

    private static void SumUpRecursive(List<int> remaining, int targetSum, List<int> listToSum)
    {
        // Sum up partial
        int sum = 0;
        foreach (int x in listToSum)
            sum += x;

        //Check sum matched
        if (sum == targetSum)
            Console.WriteLine("sum(" + string.Join(",", listToSum.ToArray()) + ")=" + targetSum);

        //Check sum passed
        if (sum >= targetSum)
            return;

        //Iterate each input character
        for (int i = 0; i < remaining.Count; i++)
        {
            //Build list of remaining items to iterate
            List<int> newRemaining = new List<int>();
            for (int j = i + 1; j < remaining.Count; j++)
                newRemaining.Add(remaining[j]);

            //Update partial list
            List<int> newListToSum = new List<int>(listToSum);
            int currentItem = remaining[i];
            newListToSum.Add(currentItem);
            SumUpRecursive(newRemaining, targetSum, newListToSum);
        }
    }'
Strider
quelle
1

PHP-Version , inspiriert von Keith Bellers C # -Version.

Die PHP-Version von bala funktionierte bei mir nicht, da ich keine Nummern gruppieren musste. Ich wollte eine einfachere Implementierung mit einem Zielwert und einem Zahlenpool. Diese Funktion beschneidet auch doppelte Einträge.

/**
 * Calculates a subset sum: finds out which combinations of numbers
 * from the numbers array can be added together to come to the target
 * number.
 * 
 * Returns an indexed array with arrays of number combinations.
 * 
 * Example: 
 * 
 * <pre>
 * $matches = subset_sum(array(5,10,7,3,20), 25);
 * </pre>
 * 
 * Returns:
 * 
 * <pre>
 * Array
 * (
 *   [0] => Array
 *   (
 *       [0] => 3
 *       [1] => 5
 *       [2] => 7
 *       [3] => 10
 *   )
 *   [1] => Array
 *   (
 *       [0] => 5
 *       [1] => 20
 *   )
 * )
 * </pre>
 * 
 * @param number[] $numbers
 * @param number $target
 * @param array $part
 * @return array[number[]]
 */
function subset_sum($numbers, $target, $part=null)
{
    // we assume that an empty $part variable means this
    // is the top level call.
    $toplevel = false;
    if($part === null) {
        $toplevel = true;
        $part = array();
    }

    $s = 0;
    foreach($part as $x) 
    {
        $s = $s + $x;
    }

    // we have found a match!
    if($s == $target) 
    {
        sort($part); // ensure the numbers are always sorted
        return array(implode('|', $part));
    }

    // gone too far, break off
    if($s >= $target) 
    {
        return null;
    }

    $matches = array();
    $totalNumbers = count($numbers);

    for($i=0; $i < $totalNumbers; $i++) 
    {
        $remaining = array();
        $n = $numbers[$i];

        for($j = $i+1; $j < $totalNumbers; $j++) 
        {
            $remaining[] = $numbers[$j];
        }

        $part_rec = $part;
        $part_rec[] = $n;

        $result = subset_sum($remaining, $target, $part_rec);
        if($result) 
        {
            $matches = array_merge($matches, $result);
        }
    }

    if(!$toplevel) 
    {
        return $matches;
    }

    // this is the top level function call: we have to
    // prepare the final result value by stripping any
    // duplicate results.
    $matches = array_unique($matches);
    $result = array();
    foreach($matches as $entry) 
    {
        $result[] = explode('|', $entry);
    }

    return $result;
}
AeonOfTime
quelle
1

Als Antwort empfohlen:

Hier ist eine Lösung mit es2015- Generatoren :

function* subsetSum(numbers, target, partial = [], partialSum = 0) {

  if(partialSum === target) yield partial

  if(partialSum >= target) return

  for(let i = 0; i < numbers.length; i++){
    const remaining = numbers.slice(i + 1)
        , n = numbers[i]

    yield* subsetSum(remaining, target, [...partial, n], partialSum + n)
  }

}

Die Verwendung von Generatoren kann tatsächlich sehr nützlich sein, da Sie die Skriptausführung sofort anhalten können, wenn Sie eine gültige Teilmenge gefunden haben. Dies steht im Gegensatz zu Lösungen ohne Generatoren (dh ohne Status), die jede einzelne Teilmenge von durchlaufen müssennumbers

feihcsim
quelle
1

Ziehen Sie zunächst 0 ab. Null ist eine Identität für die Addition, daher ist sie in diesem speziellen Fall nach den Monoidgesetzen nutzlos. Leiten Sie auch negative Zahlen ab, wenn Sie auf eine positive Zahl aufsteigen möchten. Andernfalls benötigen Sie auch eine Subtraktionsoperation.

Also ... der schnellste Algorithmus, den Sie für diesen bestimmten Job erhalten können, ist der folgende in JS.

function items2T([n,...ns],t){
    var c = ~~(t/n);
    return ns.length ? Array(c+1).fill()
                                 .reduce((r,_,i) => r.concat(items2T(ns, t-n*i).map(s => Array(i).fill(n).concat(s))),[])
                     : t % n ? []
                             : [Array(c).fill(n)];
};

var data = [3, 9, 8, 4, 5, 7, 10],
    result;

console.time("combos");
result = items2T(data, 15);
console.timeEnd("combos");
console.log(JSON.stringify(result));

Dies ist ein sehr schneller Algorithmus, aber wenn Sie das dataArray absteigend sortieren , wird es noch schneller. Die Verwendung .sort()ist unbedeutend, da der Algorithmus viel weniger rekursive Aufrufe enthält.

Reduzieren
quelle
Nett. Es zeigt, dass Sie ein erfahrener Programmierer sind :)
James P.
1

Perl-Version (der führenden Antwort):

use strict;

sub subset_sum {
  my ($numbers, $target, $result, $sum) = @_;

  print 'sum('.join(',', @$result).") = $target\n" if $sum == $target;
  return if $sum >= $target;

  subset_sum([@$numbers[$_ + 1 .. $#$numbers]], $target, 
             [@{$result||[]}, $numbers->[$_]], $sum + $numbers->[$_])
    for (0 .. $#$numbers);
}

subset_sum([3,9,8,4,5,7,10,6], 15);

Ergebnis:

sum(3,8,4) = 15
sum(3,5,7) = 15
sum(9,6) = 15
sum(8,7) = 15
sum(4,5,6) = 15
sum(5,10) = 15

Javascript-Version:

const subsetSum = (numbers, target, partial = [], sum = 0) => {
  if (sum < target)
    numbers.forEach((num, i) =>
      subsetSum(numbers.slice(i + 1), target, partial.concat([num]), sum + num));
  else if (sum == target)
    console.log('sum(%s) = %s', partial.join(), target);
}

subsetSum([3,9,8,4,5,7,10,6], 15);

Javascript-Einzeiler, der tatsächlich Ergebnisse zurückgibt (anstatt sie zu drucken):

const subsetSum=(n,t,p=[],s=0,r=[])=>(s<t?n.forEach((l,i)=>subsetSum(n.slice(i+1),t,[...p,l],s+l,r)):s==t?r.push(p):0,r);

console.log(subsetSum([3,9,8,4,5,7,10,6], 15));

Und mein Lieblings-Einzeiler mit Rückruf:

const subsetSum=(n,t,cb,p=[],s=0)=>s<t?n.forEach((l,i)=>subsetSum(n.slice(i+1),t,cb,[...p,l],s+l)):s==t?cb(p):0;

subsetSum([3,9,8,4,5,7,10,6], 15, console.log);

niry
quelle
0
function solve(n){
    let DP = [];

     DP[0] = DP[1] = DP[2] = 1;
     DP[3] = 2;

    for (let i = 4; i <= n; i++) {
      DP[i] = DP[i-1] + DP[i-3] + DP[i-4];
    }
    return DP[n]
}

console.log(solve(5))

Dies ist eine dynamische Lösung für JS, um festzustellen, auf wie viele Arten jemand die bestimmte Summe erhalten kann. Dies kann die richtige Lösung sein, wenn Sie über die Komplexität von Zeit und Raum nachdenken.

Dheerendra Dev
quelle
0
import java.util.*;

public class Main{

     int recursionDepth = 0;
     private int[][] memo;

     public static void main(String []args){
         int[] nums = new int[] {5,2,4,3,1};
         int N = nums.length;
         Main main =  new Main();
         main.memo = new int[N+1][N+1];
         main._findCombo(0, N-1,nums, 8, 0, new LinkedList() );
         System.out.println(main.recursionDepth);
     }


       private void _findCombo(
           int from,
           int to,
           int[] nums,
           int targetSum,
           int currentSum,
           LinkedList<Integer> list){

            if(memo[from][to] != 0) {
                currentSum = currentSum + memo[from][to];
            }

            if(currentSum > targetSum) {
                return;
            }

            if(currentSum ==  targetSum) {
                System.out.println("Found - " +list);
                return;
            }

            recursionDepth++;

           for(int i= from ; i <= to; i++){
               list.add(nums[i]);
               memo[from][i] = currentSum + nums[i];
               _findCombo(i+1, to,nums, targetSum, memo[from][i], list);
                list.removeLast();
           }

     }
}
Neel Salpe
quelle
0

Die Javascript-Lösung hat mir nicht gefallen. Ich habe gesehen, warum ich eine für mich selbst erstellt habe, indem ich sie teilweise angewendet, geschlossen und rekursiv gemacht habe:

Ok, ich war hauptsächlich besorgt darüber, ob das Kombinationsarray das Anforderungsziel erfüllen könnte, aber mit diesem Ansatz können Sie beginnen, den Rest der Kombinationen zu finden

Hier setzen Sie einfach das Ziel und übergeben das Kombinationsarray.

function main() {
    const target = 10
    const getPermutationThatSumT = setTarget(target)
    const permutation = getPermutationThatSumT([1, 4, 2, 5, 6, 7])

    console.log( permutation );
}

die aktuelle Implementierung, die ich mir ausgedacht habe

function setTarget(target) {
    let partial = [];

    return function permute(input) {
        let i, removed;
        for (i = 0; i < input.length; i++) {
            removed = input.splice(i, 1)[0];
            partial.push(removed);

            const sum = partial.reduce((a, b) => a + b)
            if (sum === target) return partial.slice()
            if (sum < target) permute(input)

            input.splice(i, 0, removed);
            partial.pop();
        }
        return null
    };
}
Luillyfe
quelle