Поиск всех возможных комбинаций чисел для достижения заданной суммы - PullRequest
Новая
       61

Поиск всех возможных комбинаций чисел для достижения заданной суммы

195 голосов
/ 08 января 2011

Как бы вы провели тестирование всех возможных комбинаций дополнений из заданного набора чисел, чтобы они складывались до заданного конечного числа?

Пример:

  • Набор чисел для добавления: {1,5,22,15,0, ...}
  • Желаемый результат: 12345

Ответы [ 25 ]

213 голосов
/ 08 января 2011

Эта проблема может быть решена с помощью рекурсивных комбинаций всех возможных сумм, отфильтровывающих те, которые достигают цели. Вот алгоритм на 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

Этот тип алгоритмов очень хорошо объяснен в следующей Стендфордской лекции по абстрактному программированию - это видео очень рекомендуется, чтобы понять, как работает рекурсия для создания перестановок решений.

Редактировать

Выше, как функция генератора, что делает его немного более полезным. Требуется Python 3.3+ из-за 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)

Вот Java-версия того же алгоритма: 

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

Это точно такая же эвристика. Моя Java немного ржавая, но я думаю, что это легко понять.

C # преобразование решения Java: (автор @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);
    }
}

Рубиновый раствор: (автор @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)

Редактировать: обсуждение сложности

Как уже упоминали другие, это NP-сложная проблема . Его можно решить за экспоненциальное время O (2 ^ n), например, при n = 10 будет 1024 возможных решения. Если цели, которые вы пытаетесь достичь, находятся в низком диапазоне, то этот алгоритм работает. Так, например:

subset_sum([1,2,3,4,5,6,7,8,9,10],100000) генерирует 1024 ветви, потому что цель никогда не сможет отфильтровать возможные решения.

С другой стороны, subset_sum([1,2,3,4,5,6,7,8,9,10],10) генерирует только 175 ветвей, потому что цель для достижения 10 получает возможность отфильтровать множество комбинаций.

Если N и Target - большие числа, следует перейти к приблизительной версии решения.

31 голосов
/ 08 января 2011

В Haskell : 

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

И J : 

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

Как вы можете заметить, оба используют один и тот же подход иразделите задачу на две части: сгенерируйте каждого члена набора мощности и проверьте сумму каждого члена до цели.

Существуют и другие решения, но это самое простое.

Вам нужнопомочь с одним или найти другой подход?

30 голосов
/ 20 ноября 2012

Решение этой проблемы было дано миллион раз в Интернете. Задача называется Проблема смены монет . Решения можно найти в http://rosettacode.org/wiki/Count_the_coins, а математическую модель - в http://jaqm.ro/issues/volume-5,issue-2/pdfs/patterson_harmel.pdf (или в Google проблема замены монет ).

Кстати, решение Scala от Tsagadai интересно. В этом примере выводится либо 1, либо 0. В качестве побочного эффекта в консоли отображаются все возможные решения. Он отображает решение, но никак не может его использовать.

Чтобы быть максимально полезным, код должен возвращать List[List[Int]], чтобы можно было получить номер решения (длина списка списков), «лучшее» решение (самый короткий список) или все возможные решения.

Вот пример. Это очень неэффективно, но легко понять. 

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

При запуске отображается: 

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() может использоваться сама по себе, и результат может быть дополнительно проанализирован для отображения «наилучшего» решения (самый короткий список) или количества решений (количество списков).

Обратите внимание, что даже в этом случае требования могут быть не полностью выполнены. Может случиться так, что порядок каждого списка в решении будет значительным. В таком случае каждый список должен дублироваться столько раз, сколько существует комбинация его элементов. Или нас могут интересовать только разные комбинации.

Например, мы можем считать, что List(5, 10) должно давать две комбинации: List(5, 10) и List(10, 5). Для List(5, 5, 5) это может дать три комбинации или только одну, в зависимости от требований. Для целых чисел три перестановки эквивалентны, но если мы имеем дело с монетами, как в «проблеме смены монет», они не являются.

В требованиях также не указан вопрос о том, можно ли использовать каждый номер (или монету) только один или несколько раз. Мы могли бы (и мы должны!) Обобщить проблему в список списков вхождений каждого числа. В реальной жизни это переводится как «как можно заработать определенную сумму денег с помощью набора монет (а не набора ценностей монет)». Первоначальная проблема - это только частный случай этой проблемы, когда у нас есть столько экземпляров каждой монеты, сколько необходимо, чтобы получить общую сумму для каждой монеты достоинством.

25 голосов
/ 16 июня 2015

Версия 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
11 голосов
/ 09 мая 2012

C # версия ответа с кодом @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>());
}
9 голосов
/ 19 марта 2013

C ++ версия того же алгоритма 

#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;
}
5 голосов
/ 16 мая 2012

Другое решение на Python - использовать модуль itertools.combinations следующим образом: 

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

Выход: [(8, 7), (5, 10), (3, 8, 4), (3, 5, 7)]

4 голосов
/ 21 сентября 2012

Я думал, что воспользуюсь ответом на этот вопрос, но не смог, так что вот мой ответ. Он использует измененную версию ответа в Структура и интерпретация компьютерных программ . Я думаю, что это лучшее рекурсивное решение, и оно должно больше радовать пуристов.

Мой ответ на языке Scala (и извиняюсь, если мой Scala отстой, я только начал его изучать). Сумасшествие findSumCombination заключается в сортировке и уникальном исходном списке рекурсии для предотвращения дублирования. 

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

Чтобы использовать это: 

 > findSumCombinations(12345, List(1,5,22,15,0,..))
 * Prints a whole heap of lists that will sum to the target *
4 голосов
/ 26 января 2012 
Thank you.. ephemient

Я преобразовал вышеуказанную логику из python в 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();
}
?>
3 голосов
/ 08 августа 2016

Вот версия Java, которая хорошо подходит для малого N и очень большой целевой суммы, когда сложность O(t*N) (динамическое решение) больше, чем экспоненциальный алгоритм. Моя версия использует встречу в середине атаки, а также немного смещается, чтобы уменьшить сложность от классического наивного O(n*2^n) до O(2^(n/2)).

Если вы хотите использовать это для наборов с количеством элементов от 32 до 64, вы должны изменить int, который представляет текущее подмножество в функции шага, на long, хотя производительность, очевидно, резко уменьшится с увеличением размера набора , Если вы хотите использовать это для набора с нечетным числом элементов, вы должны добавить 0 к набору, чтобы сделать его четным. 

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;
    }
}
Страница:
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.

Похожие темы

...