동적 양을 충당하기 위해 가능한 모든 값 조합을 계산하는 방법은 무엇입니까?

Question

제공된 다리의 양을 최소한 커버하는 데 필요한 '파이핑'의 가능한 모든 고유 한 조합을 반환하려고합니다.

이 문제는 일반적인 동전 변경 알고리즘과 유사합니다.

파이프가 10 ', 25'및 50 '단위로 증가합니다.

나는 가까운 것으로 보이는 here과 here의 예제를 살펴 봤지만 간단히 계산하지 않고 모든 가능한 조합을 반환하고 싶습니다.

이

let allCombos = []; 
    let pipeAmounts = [50, 25, 10]; 

    function findPiping (feet, index, combo) { 
    if (index > pipeAmounts-1) { 
     return; 
    } 
    let makeCombos = (amountOfFeet, index, combo) => { 
     let currentPipe = pipeAmounts[index]; 
     let newFeet = amountOfFeet - currentPipe; 

     combo.push(currentPipe); 

     if (newFeet >= currentPipe) { 
     makeCombos(newFeet, index, combo); 
     } 

     if (newFeet < currentPipe && newFeet > 0) { 
     makeCombos(newFeet, index, combo); 

     } 
     if (newFeet < 0) { 
     allCombos.push(combo); 
     combo = []; 
     makeCombos(feet, index+1, combo); 
     } 
    }; 
    makeCombos(feet, index, combo); 
    } 
    findPiping(60, 0, []); 
    console.log('allCombos', allCombos) 

현재 내 코드는 단지 2 개의 조합을 생성합니다 여기

내 현재 코드입니다.

필요한 발의 양을 모두 포함하는 가능한 조합을 어떻게 찾을 수 있습니까?

Answer 1

여기에 적어도 feet을 포함하는 유효한 조합을 모두 반환하는 재귀가 있으며, 이는 무제한으로 선택할 수있는 선택 항목이 amounts 인 경우에 해당합니다.

function f(feet, amounts, i, combo){ 
 
    if (feet <= 0 || i == amounts.length) 
 
    return [combo]; 
 
    
 
    if (i == amounts.length - 1){ 
 
    while (feet > 0){ 
 
     combo.push(amounts[i]); 
 
     feet -= amounts[i]; 
 
    } 
 
    return [combo]; 
 
    } 
 

 
    let combos = f(feet, amounts, i+1, combo.slice()); 
 

 
    while (feet > 0){ 
 
    combo.push(amounts[i]); 
 

 
    feet -= amounts[i]; 
 

 
    combos = combos.concat(
 
     f(feet, amounts, i+1, combo.slice()) 
 
    ); 
 
    } 
 
    
 
    return combos; 
 
} 
 

 
let pipes = [50, 25, 10]; 
 

 
console.log(JSON.stringify(f(60, pipes, 0, [])));