找到满足约束的所有组合？

Question

我的问题可以简化如下

有 s 个箱子，每个箱子内有 k 个数字。
一个组合由每个 bin 中的一个数字组成，因此总共有 k^s 种可能的组合。
组合的分数是它包含的 s 个数字的总和。

如何找到分数小于某个值 r 的所有组合？

现在我正在做的是，
1) 对每个 bin 中的数字进行排序。
2) 从一个优先级队列开始，该队列只包含每个 bin 中最小数字的组合。
3) 从队列中弹出一个组合，将该组合的 s children 添加到队列中。（child 个组合是将组合中的一个数字替换为同一容器中下一个更大的数字，因此有 s children 个组合。）
4) 重复3) 直到弹出的组合大于r.

假设我们找到n个小于r的组合，则该算法的时间复杂度为O(nlog(s-1)n + sklogk).

当然这个算法不是最优的。例如，我们可以从已知的下界开始，而不是从最小的组合开始。而且我有点感觉这里也可以应用动态规划，但是我没有弄清楚如何去做。

欢迎任何建议，谢谢。

Answer 1

对 bin 进行排序后，您可以使用递归算法，使用下一个 bin 中的元素扩展部分选择，直到选择完成（或超过总和限制）。完成后，它会添加到结果中。通过回溯，所有有效选择都添加到结果中。

这是一些伪代码。最后一个参数既是输入又是输出：

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)

这是 JavaScript 中的一个实现：

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);

找到满足约束的所有组合？

find all combinations that satisfies the constraint?

algorithm

search

combinations

combinatorics

discrete-mathematics