番号の再利用によるサブセットの合計が許可されました。

Question

私は正の整数のリストを持っています。 15, 29, 110であり、ターゲットは、 44。私はターゲットに合計する可能性のあるすべての組み合わせを見つけることを試みていますが、重要なことに、セット内の数字は複数回使用できます。

Target = 44 
Result = 1x15, 1x29 

Target = 307 
Result = 2x110, 3x29 

私は、組み合わせが各番号の1つ以上でない場合に動作する動的プログラミングソリューションを見つけました。したがって、Target 44は動作しますが、私の307の例は返されません。

倍数や数値の再利用はどのように行うことができますか？

function subset(people, min, max) 
{ 
    var subsets = []; 
    subsets[0] = ''; 

    for (var person in people) 
    { 
    for (var s = min-1; s >= 0; --s) 
    { 
     if (s in subsets) 
     { 
     var sum = s + people[person]; 

     if (!(sum in subsets)) 
     { 
      subsets[sum] = subsets[s] + ' ' + person; 

      if (sum >= min && sum <= max) 
      { 
      return subsets[sum]; 
      } 
     } 
     } 
    } 
    } 

    return 'Not found'; 
} 

var p = { 
    optionA:15, 
    optionB:29, 
    optionC:110 
}; 
var qty = 307; 
console.log(subset(p, qty, qty)); 

Answer 1

この再帰的なソリューション試してください：あなたはsubsets[]配列のすべての項目を記入し、このアプローチを使用

for (var s = 0; s <= wantedSum - people[person] ; s++) 

：ような方法で、第二のループ

function subset(people, min, max) { 
 
\t const pairs = Object.entries(people), 
 
\t \t results = [], 
 
\t \t getSum = multiplications => multiplications.reduce((sum, multiplicator, position) => 
 
\t \t \t sum + pairs[position][1] * multiplicator, 0), 
 
\t \t formatResult = result => result.map(multiplications => 
 
\t \t \t multiplications.reduce((res, multiplicator, position) => 
 
\t \t \t (multiplicator > 0 ? res.push(`${multiplicator}x${pairs[position][1]}`) : 
 
\t \t \t \t res, res), [])); 
 
\t function findSums(multiplications, position) { 
 
\t \t let s; 
 
\t \t while((s = getSum(multiplications)) <= max) { 
 
\t \t \t if (s >= min) { 
 
\t \t \t \t results.push([...multiplications]); 
 
\t \t \t } 
 
\t \t \t if (position < pairs.length - 1) { 
 
\t \t \t \t const m = [...multiplications], 
 
\t \t \t \t \t nextPosition = position + 1; 
 
\t \t \t \t m[nextPosition]++; 
 
\t \t \t \t findSums(m, nextPosition); 
 
\t \t \t } 
 
\t \t \t multiplications[position]++; 
 
\t \t } 
 
\t } 
 
\t findSums(pairs.map(_ => 0), 0); 
 
\t return results.length > 0 ? formatResult(results) : "Not found"; 
 
} 
 

 
var p = { 
 
    optionA:15, 
 
    optionB:29, 
 
    optionC:110 
 
}; 
 
var qty = 307; 
 
console.log(subset(p, qty, qty));

Answer 2

変更を\ listインデックスは複数ですpeople[person]（単一エントリではなく）です。たとえば、値3の場合は、3,6,9,12 ...の項目を入力します。