[algorithm] 주어진 합계에 도달하기 위해 가능한 모든 숫자 조합 찾기
주어진 N숫자 집합에서 가능한 모든 추가 조합을 테스트 하여 주어진 최종 숫자에 더하는 방법은 무엇입니까?
간단한 예 :
- 추가 할 숫자 세트 :
N = {1,5,22,15,0,...} - 원하는 결과 :
12345
답변
이 문제는 대상에 도달하는 합계를 필터링하는 가능한 모든 합계의 재귀 조합으로 해결할 수 있습니다. 다음은 파이썬의 알고리즘입니다.
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
이 유형의 알고리즘은 다음 Standford의 추상 프로그래밍 강의 에서 잘 설명되어 있습니다. 이 비디오는 재귀가 솔루션의 순열을 생성하는 방법을 이해하는 데 매우 권장됩니다.
편집하다
위의 생성기 함수로 좀 더 유용합니다. 때문에 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는 약간 녹슬지 만 이해하기 쉽다고 생각합니다.
Java 솔루션의 C # 변환 : (@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-hard 문제 입니다. 지수 시간 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)도달 할 대상이 10여러 조합을 필터링 하기 때문에 175 개의 분기 만 생성합니다 .
경우 N와 Target하나가 솔루션의 대략적인 버전으로 이동해야 큰 숫자입니다.
답변
이 문제의 해결책은 인터넷에서 백만 번 주어졌습니다. 문제는 동전 변경 문제 입니다. http://rosettacode.org/wiki/Count_the_coins 에서 솔루션을 찾을 수 있고 http://jaqm.ro/issues/volume-5,issue-2/pdfs/patterson_harmel.pdf (또는 Google 코인 변경) 에서 수학적 모델을 찾을 수 있습니다. 문제 ).
그런데 Tsagadai의 Scala 솔루션은 흥미 롭습니다. 이 예제는 1 또는 0을 생성합니다. 부작용으로 콘솔에 가능한 모든 솔루션이 나열됩니다. 솔루션을 표시하지만 어떤 식 으로든 사용할 수 없게합니다.
가능한 한 유용하도록 코드는 List[List[Int]]솔루션 수 (목록 목록의 길이), “최상의”솔루션 (가장 짧은 목록) 또는 가능한 모든 솔루션을 얻을 수 있도록 a 를 반환해야 합니다.
다음은 예입니다. 매우 비효율적이지만 이해하기 쉽습니다.
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)는 요구 사항에 따라 세 가지 조합 또는 하나를 줄 수 있습니다. 정수의 경우 세 순열은 동일하지만 “코인 변경 문제”와 같이 동전을 다루는 경우에는 그렇지 않습니다.
또한 요구 사항에는 각 숫자 (또는 동전)를 한 번 또는 여러 번 사용할 수 있는지에 대한 질문이 나와 있지 않습니다. 문제를 각 숫자의 발생 목록으로 일반화 할 수 있습니다. 이것은 실생활에서 “일련의 동전 (일련의 동전 가치가 아닌)으로 일정 금액을 벌 수있는 방법은 무엇인가”로 해석됩니다. 원래 문제는이 문제의 특별한 경우이며, 각 단일 코인 값으로 총액을 만드는 데 필요한만큼의 각 코인이 발생합니다.
답변
에서 하스켈 :
filter ((==) 12345 . sum) $ subsequences [1,5,22,15,0,..]그리고 J :
(]#~12345=+/@>)(]<@#~[:#:@i.2^#)1 5 22 15 0 ...알다시피, 동일한 접근 방식을 취하고 문제를 두 부분으로 나눕니다. 전원 세트의 각 멤버를 생성하고 각 멤버의 합계를 대상으로 확인하십시오.
다른 솔루션이 있지만 가장 간단합니다.
도움이 필요하거나 다른 접근법을 찾고 있습니까?
답변
자바 스크립트 버전 :
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답변
동일한 알고리즘의 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;
}답변
@msalvadores 코드 답변의 C # 버전
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>());
}답변
나는이 질문에 대한 답변을 사용할 것이라고 생각했지만 할 수 없었으므로 여기에 내 대답이 있습니다. 컴퓨터 프로그램의 구조 및 해석 에서 수정 된 버전의 답변을 사용하고 있습니다. 나는 이것이 더 나은 재귀 솔루션이라고 생각하며 순수 주의자들을 더 기쁘게해야합니다.
내 대답은 스칼라에 있습니다 (그리고 스칼라가 짜증 나면 사과하기 시작했습니다). findSumCombinations 의 크래 기는 재귀를 방지하기 위해 원래 목록을 정렬하고 고유 화하여 속력 을 방지하는 것입니다.
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 *