합계 조합 목록

Question

나는이 문제에 대한 알고리즘을 필요

는 n은 자연수의 X1, X2, ..., XN, 다수의 S와 K의 집합을 감안할 때. 집합에서 선택한 k 개의 합 (합계 수가 여러 번 선택 될 수 있음)을 합계 S로 형성하십시오.

다르게 표기 됨 : S의 가능한 모든 조합을 경계로 나열하십시오. n < = 256, x < = 1000, k < = 32

예

problem instance: {1,2,5,9,11,12,14,15}, S=30, k=3 
    There are 4 possible combinations 
    S=1+14+15, 2+14+14, 5+11+15, 9+9+12. 

이러한 경계를 사용하면 무차별 대입을 사용하는 것이 불가능하지만 동적 프로그래밍이 좋은 접근 방법이라고 생각합니다.

스키마는 다음과 같습니다. t [m, v] = m 개의 숫자로 구성된 합계 v의 조합 수입니다.

1. Initialize t[1,x(i)], for every i. 
2. Then use formula t[m,v]=Sum(t[m-1,v-x(i)], every i satisfied v-x(i)>0), 2<=m<=k. 
3. After obtaining t[k,S], I can trace back to find all the combinations. 

딜레마가 t를이다의 m, V] 중복 교환 적 조합에 의해 증가 될 수있다 예를 들어, t [2.16] = 제 16 = 1 + 15 + 1 15 2. 또한, 최종 결과 f [3,30]은 1 + 14 + 15, 1 + 15 + 14, ..., 2 + 14 + 14,14 + 2 + 14, ...

대칭 순열을 제거하는 방법은 무엇입니까? 미리 감사드립니다.

Answer 1

x 요소를 선택하는 순서에 따라 순열을 제거 할 수 있습니다. 테이블을 트리플로 만듭니다 t[m, v, n] = 합계가 v 인 수는 m 숫자로 구성되어 있습니다. x1..xn입니다. 이제 t[m, v, n] = t[m, v, n-1] + t[m-1, v-x_n, n]을 관찰하십시오. 이것은 x의 모양과 반대 순서로 summands를 생성함으로써 순열 문제를 해결합니다. 예를 들어 15 + 14 + 1과 14 + 14 + 2를 생성하지만 14 + 15 + 1은 생성하지 않습니다.

(당신은 아마 느리게 계산한다, 그래서 당신은 아마, 전체 테이블을 작성 할 필요가 없습니다. 사실, memoized 재귀 함수가 여기에 원하는 아마도)