Znajdowanie wszystkich możliwych kombinacji liczb w celu osiągnięcia określonej sumy

232

Jak poszedłbyś przetestować wszystkie możliwe kombinacje dodatków z danego zestawu Nliczb, aby sumowały się one do podanej liczby końcowej?

Krótki przykład:

  • Zestaw liczb do dodania: N = {1,5,22,15,0,...}
  • Pożądany rezultat: 12345
James P.
źródło
@James - Myślę, że twój problem wymaga wyjaśnienia. Jakie są zasady? Czy możesz wybrać tylko dowolne liczby? Jakie liczby są w zestawie? Jakie są twoje ograniczenia?
jmort253
9
Artykuł w Wikipedii ( en.wikipedia.org/wiki/Subset_sum_problem ) wspomina nawet, że ten problem jest dobrym wprowadzeniem do klasy problemów NP-zupełnych.
user57368
1
@ jmort253: Nie sądzę, że istnieją jakieś ograniczenia inne niż posiadanie zestawu liczb całkowitych, które są dodatnie i niższe niż liczba podana jako cel. Można użyć dowolnej kombinacji liczb. Nie jest to praca domowa, ale rodzaj problemu, który możesz rozwiązać, jeśli ubiegasz się o niektóre prace. Zwykle mogę wymyślić algorytm, gdy jest to potrzebne, ale nie jestem pewien, jak wyświetlić coś takiego. Trzeba go jakoś rozłożyć (rekurencyjny?).
James P.
3
@James, Potrzebujesz kombinacji, czy tylko liczby podzbiorów, które sumują się do sumy?
st0le
6
Czy możemy użyć tego samego elementu oryginalnego zestawu więcej niż jeden raz? Na przykład, jeśli dane wejściowe wynoszą {1,2,3,5}, a cel 10, czy 5 + 5 = 10 jest akceptowalnym rozwiązaniem?
alampada

Odpowiedzi:

248

Problem ten można rozwiązać za pomocą rekurencyjnych kombinacji wszystkich możliwych kwot odfiltrowujących te, które osiągają cel. Oto algorytm w Pythonie:

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

Tego rodzaju algorytmy są bardzo dobrze wyjaśnione w następującym wykładzie Standford's Abstract Programming - ten film jest bardzo godny polecenia, aby zrozumieć, jak rekurencja działa w celu generowania permutacji rozwiązań.

Edytować

Powyżej jako funkcja generatora, dzięki czemu jest nieco bardziej przydatna. Wymaga Python 3.3+ z powodu 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)

Oto wersja Java tego samego algorytmu:

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);
    }
}

To jest dokładnie ta sama heurystyka. Moja Java jest trochę zardzewiała, ale myślę, że jest łatwa do zrozumienia.

Konwersja C # rozwiązania Java: (autor: @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);
    }
}

Rozwiązanie Ruby: (autor @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)

Edycja: dyskusja złożoności

Jak wspominają inni, jest to trudny problem NP . Można go rozwiązać w czasie wykładniczym O (2 ^ n), na przykład dla n = 10 będzie 1024 możliwych rozwiązań. Jeśli cele, które próbujesz osiągnąć, znajdują się w niskim zakresie, algorytm działa. Na przykład:

subset_sum([1,2,3,4,5,6,7,8,9,10],100000) generuje 1024 gałęzie, ponieważ cel nigdy nie odfiltruje możliwych rozwiązań.

Z drugiej strony subset_sum([1,2,3,4,5,6,7,8,9,10],10)generuje tylko 175 gałęzi, ponieważ cel do osiągnięcia 10pozwala odfiltrować wiele kombinacji.

Jeśli Ni Targetsą dużymi liczbami, należy przejść do przybliżonej wersji rozwiązania.

Manuel Salvadores
źródło
1
Optymalizacja Java: ArrayList <Integer> czesciowy_rec = nowy ArrayList <Integer> (częściowy); czesciowy_rec.add (n); robi to kopię częściową. i w ten sposób dodaje O (N). Lepszym sposobem jest po prostu „częściowe.add (n)” wykonanie rekurencji, a następnie „częściowe. Usunięcie (częściowe.size -1). Zmieniłem kod, aby się upewnić. Działa dobrze
Christian Bongiorno
4
To rozwiązanie nie działa we wszystkich przypadkach. Rozważ [1, 2, 0, 6, -3, 3], 3- wyświetla tylko [1,2], [0,3], [3]przy brakujących przypadkach, takich jak[6, -3, 3]
LiraNuna,
11
To również nie działa dla każdej kombinacji, na przykład [1, 2, 5], 5tylko wyjść [5], kiedy [1, 1, 1, 1, 1], [2, 2, 1]i [2, 1, 1, 1]są rozwiązaniami.
cbrad
3
@cbrad z powodu i+1in remaining = numbers[i+1:]. Wygląda na to, że ten algorytm nie zezwala na duplikaty.
Leonid Wasilew
1
@cbrad dostać również rozwiązania w tym duplikaty jak [1, 1, 3]spojrzeć na stackoverflow.com/a/34971783/3684296 (Python)
Mesa
36

Rozwiązanie tego problemu podano milion razy w Internecie. Problem nazywa się Problem zmiany monety . Rozwiązania można znaleźć na stronie http://rosettacode.org/wiki/Count_the_coins, a jej matematyczny model na stronie http://jaqm.ro/issues/volume-5,issue-2/pdfs/patterson_harmel.pdf (lub zmiana monety Google problem ).

Nawiasem mówiąc, interesujące jest rozwiązanie Scala firmy Tsagadai. Ten przykład daje 1 lub 0. Jako efekt uboczny, wypisuje na konsoli wszystkie możliwe rozwiązania. Wyświetla rozwiązanie, ale nie udaje się go w żaden sposób wykorzystać.

Aby być jak najbardziej użytecznym, kod powinien zwrócić a List[List[Int]], aby umożliwić uzyskanie liczby rozwiązań (długość listy list), „najlepszego” rozwiązania (najkrótsza lista) lub wszystkich możliwych rozwiązań.

Oto przykład. Jest bardzo nieefektywny, ale łatwo go zrozumieć.

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")
}

Po uruchomieniu wyświetla:

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)

sumCombinations()Funkcja może być stosowany sam, a wynik może być dalej analizowane w celu wyświetlenia „najlepsze” rozwiązanie (najkrótsza listy) lub szereg rozwiązań (liczbie List).

Pamiętaj, że nawet w ten sposób wymagania mogą nie być w pełni spełnione. Może się zdarzyć, że kolejność każdej listy w rozwiązaniu będzie znacząca. W takim przypadku każda lista musiałaby zostać zduplikowana tyle razy, ile jest kombinacji jej elementów. Lub możemy być zainteresowani tylko różnymi kombinacjami.

Na przykład możemy rozważyć, że List(5, 10)powinny dać dwie kombinacje: List(5, 10)i List(10, 5). Na List(5, 5, 5)to może dać trzy kombinacje czy tylko jeden, w zależności od wymagań. W przypadku liczb całkowitych trzy permutacje są równoważne, ale jeśli mamy do czynienia z monetami, jak w przypadku „problemu wymiany monet”, nie są.

W wymaganiach nie podano również, czy każdy numer (lub moneta) może być użyty tylko raz, czy wiele razy. Możemy (i powinniśmy!) Uogólnić problem na listę list występowania każdej liczby. Przekłada się to w rzeczywistości na „jakie są możliwe sposoby zarabiania pewnej ilości pieniędzy za pomocą zestawu monet (a nie zestawu wartości monet)”. Pierwotny problem to tylko szczególny przypadek tego przypadku, w którym mamy tyle wystąpień każdej monety, ile potrzeba, aby uzyskać całkowitą kwotę przy każdej wartości monety.

Pierre-Yves Saumont
źródło
14
Ten problem nie jest dokładnie taki sam jak problem zmiany monety. OP prosi o wszystkie kombinacje, nie tylko minimalne. I przypuszczalnie liczby całkowite w zestawie mogą być ujemne. W związku z tym niektóre optymalizacje problemu zmiany monety nie są możliwe w przypadku tego problemu.
ThomasMcLeod
5
a także ten problem pozwala na powtarzanie przedmiotów, nie jestem pewien, czy OP tego chciał, ale bardziej problem plecakowy
klub
34

W Haskell :

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

I J :

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

Jak możesz zauważyć, obaj zastosuj to samo podejście i podziel problem na dwie części: wygeneruj każdy element zestawu mocy i sprawdź sumę każdego elementu do celu.

Istnieją inne rozwiązania, ale jest to najprostsze.

Czy potrzebujesz pomocy z jednym z nich lub szukasz innego podejścia?

efemeryczny
źródło
3
Wow, to całkiem zwięzły kod. Nic mi nie jest z twoją odpowiedzią. Myślę, że po prostu muszę trochę przeczytać o algorytmach w ogóle. Rzucę okiem na składnię tych dwóch języków, gdy wywołałeś moją ciekawość.
James P.
Właśnie zainstalowałem Haskell, aby to wypróbować, na pewno nie mogę go po prostu wkleić i uruchomić, not in scope: 'subsequences'jakieś wskazówki?
Hart CO
4
@HartCO nieco późno do partii, aleimport Data.List
Jir
28

Wersja Javascript:

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
źródło
Kod ma błąd w wycinku, w remaining = numbers.slice(); remaining.slice(i + 1);przeciwnym razie należy numbers.slice(i + 1);zmienić tablicę liczb
Emeeus
@Emeeus, nie sądzę, że to prawda. slicezwraca (płytką) kopię, nie modyfikuje numberstablicy.
Dario Seidl
@DarioSeidl tak, slice zwraca kopię, nie modyfikuje tablicy, o to chodzi, dlatego jeśli nie przypiszesz jej do zmiennej, nie zmienisz jej. W tym przypadku, jak rozumiem, musimy przekazać zmodyfikowaną wersję, a nie oryginalną. Zobacz to jsfiddle.net/che06t3w/1
Emeeus
1
@Redu ... na przykład łatwym sposobem na to jest to, że możemy nieznacznie zmodyfikować algorytm i użyć funkcji wewnętrznej: jsbin.com/lecokaw/edit?js,console
rbarilani
1
Podany kod niekoniecznie zawiera wszystkie kombinacje. Np. Wstawienie [1,2], 3 zwróci tylko 1 + 2 = 3, a nie 1 + 1 + 1 lub 2 + 1
JuicY_Burrito
12

Wersja C ++ tego samego algorytmu

#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
źródło
11

Wersja C # odpowiedzi na kod @msalvadores

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
źródło
4

Myślałem, że skorzystam z odpowiedzi na to pytanie, ale nie mogłem, więc oto moja odpowiedź. Wykorzystuje zmodyfikowaną wersję odpowiedzi w Strukturze i interpretacji programów komputerowych . Myślę, że jest to lepsze rozwiązanie rekurencyjne i powinno bardziej zadowolić purystów.

Moja odpowiedź jest w Scali (i przepraszam, jeśli moja Scala jest do bani, właśnie zaczęłam się uczyć). FindSumCombinations szaleństwo jest do rodzaju i niepowtarzalny oryginalnej listy do rekursji do uniknięcia powtórzeń.

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)
}

Aby go użyć:

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

przekonwertowałem powyższą logikę z Pythona na php ..

<?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
źródło
4

Innym rozwiązaniem Pythona byłoby użycie itertools.combinationsmodułu w następujący sposób:

#!/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)

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

mózg
źródło
nie działa np .: find_sum_in_list (zakres (0,8), 4). Znaleziono: [(4,), (0, 4), (1, 3), (0, 1, 3)]. Ale (2, 2) też jest opcją!
Andre Araujo
@AndreAraujo: nie ma sensu używać 0, ale jeśli użyjesz (1,8), itertools.combinations_with_replacement działa, a także zwraca 2,2.
Rubenisme,
@Rubenisme Tak, stary! Problem polegał na wymianie! Dzięki! ;-)
Andre Araujo,
4

Oto rozwiązanie w 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))
  }
}
znak
źródło
Szukam rozwiązania w języku R, ale to nie działa dla mnie. Na przykład subset_sum(numbers = c(1:2), target = 5)zwraca "sum(1+2+2)=5". Brakuje jednak kombinacji 1 + 1 + 1 + 1 + 1. W ustawianiu celów na wyższe liczby (np. 20) brakuje jeszcze większej liczby kombinacji.
Frederick
To, co opisujesz, nie jest tym, co funkcja ma zwrócić. Spójrz na zaakceptowaną odpowiedź. Powtarzanie 2 razy jest artefaktem tego, w jaki sposób R generuje i dzieli serie, a nie zamierzone zachowanie.
Mark
subset_sum(1:2, 4)nie powinien zwracać żadnych rozwiązań, ponieważ nie ma kombinacji 1 i 2, która dodaje do 4. To, co należy dodać do mojej funkcji, to ucieczka, jeśli ijest większa niż długośćnumbers
Mark
3

Oto wersja Java, która dobrze nadaje się do małej N i bardzo dużej sumy docelowej, gdy złożoność O(t*N)(rozwiązanie dynamiczne) jest większa niż algorytm wykładniczy. Moja wersja wykorzystuje spotkanie w środkowym ataku, wraz z niewielkim przesunięciem w celu zmniejszenia złożoności z klasycznego naiwnego O(n*2^n)do O(2^(n/2)).

Jeśli chcesz użyć tego dla zestawów zawierających od 32 do 64 elementów, powinieneś zmienić ten, intktóry reprezentuje bieżący podzbiór w funkcji kroku, na longchociaż wydajność wyraźnie drastycznie spadnie wraz ze wzrostem rozmiaru zestawu. Jeśli chcesz użyć tego dla zestawu z nieparzystą liczbą elementów, powinieneś dodać 0 do zestawu, aby był parzysty.

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
źródło
3

Jest to podobne do problemu wymiany monet

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 ”
źródło
2

Bardzo wydajny algorytm wykorzystujący tabele napisane kilka lat temu w c ++.

Jeśli ustawisz DRUKUJ 1, wydrukuje wszystkie kombinacje (ale nie będzie to efektywna metoda).

Jest tak wydajny, że oblicza ponad 10 ^ 14 kombinacji w czasie krótszym niż 10ms.

#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
źródło
cześć! Potrzebuję kodu, aby zrobić coś takiego, znaleźć wszystkie możliwe sumy zestawów 6 liczb na liście 60 liczb. Sumy powinny mieścić się w zakresie od min 180 do maks. 191. Czy można w tym celu dostosować ten kod? Gdzie uruchomić ten kod w chmurze? Próbowałem bezskutecznie w Codenvy
defreturn
2

Wersja Excel VBA poniżej. Musiałem zaimplementować to w VBA (nie moje preferencje, nie oceniaj mnie!) I wykorzystałem odpowiedzi z tej strony do tego podejścia. Przesyłam na wypadek, gdyby inni również potrzebowali wersji VBA.

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

Dane wyjściowe (zapisane w oknie natychmiastowym) powinny wynosić:

SUM ( {3,8,4} ) = 15
SUM ( {3,5,7} ) = 15
SUM ( {8,7} ) = 15
SUM ( {5,10} ) = 15 
CodingQuant
źródło
2

Oto lepsza wersja z lepszym formatowaniem wyjściowym i funkcjami C ++ 11:

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
źródło
2

Nierekurencyjna wersja Java, która po prostu dodaje elementy i redystrybuuje je wśród możliwych wartości. 0są ignorowane i działają na ustalonych listach (możesz się nimi bawić) lub na liście powtarzalnych liczb.

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();
        }
    }
}

Przykładowe dane wejściowe:

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

Przykładowe dane wyjściowe:

## 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
źródło
1

Aby znaleźć kombinacje za pomocą programu Excel - (jest dość łatwe). (Twój komputer nie może być zbyt wolny)

  1. Przejdź do tej strony
  2. Przejdź do strony „Suma do celu”
  3. Pobierz plik Excel „Sum to Target”.

    Postępuj zgodnie ze wskazówkami na stronie internetowej.

mam nadzieję że to pomoże.

Mark van Zoest
źródło
1

Szybka konwersja rozwiązania Java: (autor: @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
    }

}

stosowanie:

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
źródło
1

Można to również wykorzystać do wydrukowania wszystkich odpowiedzi

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();
}

Złożoność czasu ma charakter wykładniczy. Rząd 2 ^ n

Astha Gupta
źródło
1

Robiłem coś podobnego do zadania Scala. Pomysł opublikowania mojego rozwiązania tutaj:

 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
źródło
1

Przeniesiłem próbkę C # do Objective-c i nie widziałem jej w odpowiedziach:

//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
źródło
1

Odpowiedź KeithBellera z nieznacznie zmienionymi nazwami zmiennych i kilkoma komentarzami.

    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
źródło
1

Wersja PHP , inspirowana wersją C # Keitha Bellera.

Wersja PHP bala dla mnie nie działała, ponieważ nie musiałem grupować numerów. Chciałem prostszej implementacji z jedną wartością docelową i pulą liczb. Ta funkcja również przycina wszelkie zduplikowane wpisy.

/**
 * 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
źródło
1

Zalecane jako odpowiedź:

Oto rozwiązanie wykorzystujące generatory es2015 :

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)
  }

}

Korzystanie z generatorów może być bardzo przydatne, ponieważ umożliwia wstrzymanie wykonywania skryptu natychmiast po znalezieniu prawidłowego podzbioru. Jest to sprzeczne z rozwiązaniami bez generatorów (tj. Bez stanu), które muszą iterować przez każdy pojedynczy podzbiórnumbers

feihcsim
źródło
1

Po pierwsze odejmij 0. Zero jest identyfikatorem do dodania, więc w tym konkretnym przypadku jest bezużyteczne przez prawa monoidów. Odejmij także liczby ujemne, jeśli chcesz wspiąć się na liczbę dodatnią. W przeciwnym razie potrzebujesz również operacji odejmowania.

Więc ... najszybszy algorytm, jaki można uzyskać w tym konkretnym zadaniu, jest następujący w 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));

Jest to bardzo szybki algorytm, ale jeśli posortujesz datatablicę malejącą , będzie to jeszcze szybsze. Używanie .sort()jest nieznaczne, ponieważ algorytm zakończy się znacznie mniej rekurencyjnymi wywołaniami.

Redu
źródło
Miły. To pokazuje, że jesteś doświadczonym programistą :)
James P.
1

Wersja Perla (wiodąca odpowiedź):

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);

Wynik:

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

Wersja Javascript:

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);

Jednoliniowy skrypt Javascript, który faktycznie zwraca wyniki (zamiast go drukować):

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));

I mój ulubiony, liniowiec z oddzwanianiem:

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
źródło
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))

Jest to dynamiczne rozwiązanie dla JS, które informuje, w jaki sposób każdy może uzyskać określoną sumę. To może być właściwe rozwiązanie, jeśli myślisz o złożoności czasu i przestrzeni.

Dheerendra Dev
źródło
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
źródło
0

Nie podobało mi się rozwiązanie JavaScript. Widziałem, dlaczego buduję jeden dla siebie, stosując częściowe stosowanie, zamykanie i rekurencję:

Ok, głównie martwiłem się, czy tablica kombinacji może spełnić docelowy wymóg, ale dzięki temu podejściu możesz zacząć znajdować resztę kombinacji

Tutaj wystarczy ustawić cel i przekazać tablicę kombinacji.

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

    console.log( permutation );
}

aktualnie wdrażane przeze mnie rozwiązanie

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
źródło