제약 조건을 만족하는 모든 조합을 찾으시겠습니까?

Question

내 문제는 다음과 같이 단순화 될 수 있습니다.

빈이 있습니다. 각 빈에는 k 개의 숫자가 있습니다. s입니다.
조합은 각 빈에서 하나의 숫자로 구성되므로 합계가 k^s 개의 조합이 될 수 있습니다.
조합의 점수는 포함 된 s 숫자의 합계입니다.

일부 점수가 미만인 모든 조합을 어떻게 찾을 수 있습니까?

---

은 지금 내가 뭘하는지
1) 각 빈에있는 숫자를 정렬합니다.
2) 각 bin에서 가장 작은 수의 조합 만 포함하는 우선 순위 대기열로 시작하십시오.
3) 대기열에서 조합을 팝업하고 대기열에 해당 조합의 자식을 s 개 추가하십시오. (조합의 자식은 하나의 조합을 동일한 빈의 다음 큰 숫자로 바꾸는 것으로 만들어 지므로 조합의 자식은 s입니다.)
4) 반복 3) 팝업 된 조합이 r.

r보다 작은 n 조합을 찾으면이 알고리즘의 시간 복잡도는 O(nlog(s-1)n + sklogk)이됩니다.

물론이 알고리즘은 최적이 아닙니다. 예를 들어, 가장 작은 조합으로 시작하는 대신, 알려진 하한값으로 시작할 수 있습니다. 동적 프로그래밍이 여기에 적용될 수 있다는 느낌이 들지만, 어떻게해야 하는지를 알지 못했습니다.

모든 의견을 환영합니다.

Answer 1

빈을 정렬 한 후 재귀 알고리즘을 사용할 수 있습니다. 재귀 알고리즘은 선택이 완료 될 때까지 다음 빈의 요소로 부분 선택을 확장합니다 (또는 총합을 초과합니다). 완료되면 결과에 추가됩니다. 역 추적을 통해 모든 유효한 선택 항목이 결과에 추가됩니다.

여기에 몇 가지 의사 코드가 있습니다.

function sortBins(bins) { 
 
    for (bin of bins) { 
 
    bin.sort(function (a,b) { return a-b; }); 
 
    } 
 
} 
 

 
function combinations(bins, r, selection, result) { 
 
    if (r < 0) return result; // nothing added to result 
 
    if (selection.length >= bins.length) return result.concat([selection]); 
 

 
    var bin = bins[selection.length]; 
 
    for (var i = 0; i < bin.length; i++) 
 
    result = combinations(bins, r - bin[i], selection.concat([bin[i]]), result); 
 
    return result; 
 
} 
 

 
// Test data: 
 
var r = 13; 
 
var bins = [ 
 
    [5, 2, 3], 
 
    [9, 4, 1], 
 
    [6, 5, 7] 
 
]; 
 
// Get solution: 
 
sortBins(bins); 
 
var result = combinations(bins, r, [], []); 
 
// Output results: 
 
console.log(result);

: 여기

function combinations(int[][] bins, int r, int[] selection, int[][] result): 
    if r < 0 then: 
     return 
    if selection.length >= bins.length then: 
     result.add(selection) 
     return 
    bin = bins[selection.length] 
    for (i = 0; i < bin.length; i++): 
     # Concatenate the i-th value from the bin to a new selection array 
     combinations(bins, r - bin[i], selection + bin[i], result) 

자바 스크립트의 구현 : 마지막 인자는 입력 및 출력 모두가