javascript - 允许重复使用号码的子集和

Question

我有一个正整数列表，例如15, 29, 110 和一个目标，例如44。我试图找到所有可能的组合，其总和达到目标，但重要的是，集合中的数字可以多次使用，例如

Target = 44
Result = 1x15, 1x29

Target = 307
Result = 2x110, 3x29

我找到了一种动态编程解决方案，当组合不超过每个数字一个时，该解决方案就有效。所以 Target 44 可以工作，但我的 307 示例不起作用(返回 Not Found)。

如何实现倍数或号码重复使用？

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

尝试这个递归解决方案:

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