等于或超过给定数字的所有组合

Question

它不同于硬币兑换问题link。

给定一个字典 x=[a:1,b:2,c:1,d:3,e:2]，我需要计算键的所有可能组合，使得与这些键关联的值的总和刚好超过或等于给定值，比如 5。刚好超过 5 意味着如果选择的元素小于5，我们可以再添加一个元素，即使它超过5，但一旦我们超过或等于5，就不能再添加元素。

有两个问题使我的方法变得复杂 -

请注意，某些值是重复的，例如1和2各出现两次，需要分开考虑。
在这种情况下，顺序很重要。

订购也很重要，因此 [b,c,d], [b,d,c], [c,b,d], [c,d,b], [d,b,c], [d,c,b] 全部单独包含。理想情况下，仅当我们超过 5 时排序才重要，只要总和恰好为 5，排序无关紧要。

所以上述问题的一些解决方案是 [a,b,c,d] 总和 7，[a,b,c,e] 总和 6，[b,c,d] 总和 6，[d,e] 总和 5等等

我该如何解决这个问题。我正在考虑使用硬币兑换的输出，然后将一个元素添加到每个结果列表中，但这不会涵盖所有情况。

编辑 1：构建问题的更好方法可能是找到所有组合，使得总和 (i) 等于 5 或 (ii) 刚好超过 5，因为总和直到倒数第二个元素小于 5，因此添加最后一个元素使其大于 5。一旦我们有 5 或 >5，就不会添加其他元素。

编辑 2：澄清订购问题。为了提供一些上下文，键是设备，值是它需要的资源。可用资源总数为 5。设备根据其键分配资源，即第一个键值对将首先提供服务（根据键按字母顺序排序）。对于 b，它需要 2 个，但说只有 1 个资源可用 - 它将分配 1 个，其余 1 个将在下一个运行中分配（溢出）。因此，当总和恰好为 5 时，顺序无关紧要，因为每个都得到它想要的任何东西，并且不会溢出到下一个槽。例如。 ed 和 de 意味着他们都得到了他们想要的，所以他们都应该被包括在内。但是对于仅由于添加最后一个元素而超过 5 的列表，排序很重要，因为溢出只会发生在最后一个元素上。例如。 dce 表示 d 和 c 分别得到 3 和 1，而 e 只得到 1（1 溢出到下一个运行）。类似地，ced 意味着 c 和 d 分别得到 1 和 3，d 发生溢出，因为它只被分配 1.

Answer 1

更新答案

有关要求的更多详细信息已添加到问题中。我认为这个版本适合他们。但是没有指定预期的输出结构，所以这是一个猜测。它以这样的结果数组结尾：

{initial: {a: 1, b: 2, c: 1}, last: {d: 3}}

或者像这样：

{initial: {b: 2, c: 1, e: 2}}

它首先使用函数 partitions 找到初始值的所有子集及其补集。 partitions (['a', 'b', 'c', 'd']) 将有十六个元素，包括 [['a', 'b', 'd'], ['c']]、[['b', 'd'], ['a', 'c']] 和 [[], ['a', 'b', 'c', 'd']]。

然后，对于每个分区，如果其左半部分的总和等于我们包含它的目标。如果总和小于目标，我们会在右半部分包含一个超过目标的每个值的结果。

这是 Javascript 中的一个实现：

// utility functions
const last = (xs) => 
  xs [xs .length - 1]

const partitions = (xs) => 
  xs .length === 0
    ? [[[], []]]
    : partitions (xs .slice (0, -1)) .flatMap (([p, q]) => [ 
        [[...p, last (xs)], q], 
        [p, [...q, last (xs)]] 
      ])

// helper function
const total = (xs) =>
  xs .reduce ((a, [k, v]) => a + v, 0)


// main function
const sumTo = (n, xs, parts = partitions (xs)) =>
  parts .flatMap (([incl, excl], _, __, t = total (incl)) => [
    ... (t == n ? [{initial: incl}] : []),
    ... (t < n
           ? excl .filter (([k, v]) => v + t > n) 
                  .map (e => ({initial: incl, last: [e]}))
           : []
        )
  ])


// public function
const subsetSum = (n, dict) =>
  sumTo (n, Object.entries (dict))
    .map (({initial, last}) => ({
      initial: Object .fromEntries (initial), 
      ... (last ? {last: Object .fromEntries (last)} : {})
    }))


// sample data
const dict = {a: 1, b: 2, c: 1, d: 3, e: 2}


// demo
console .log (subsetSum (5, dict))

.as-console-wrapper {max-height: 100% !important; top: 0}

我们从一个简单的辅助函数 last 开始，它只是选择数组的最后一个元素。然后我们有 partition，上面已经描述过了。我们的主要功能是 sumTo，它完成所描述的工作。它的输入是目标数字和类似 [['a', '1], ['b', 2'], ['c', 1], ['d', 3], ['e', 2]] 的结构，它很容易从字典中导出，但更容易使用。它 returns 是一个具有两个属性的对象，类似于 {initial: [['a', 1], ['b', 2], ['c', 1]], last: [['d', 3]]}。最后我们得到了 public 函数 subsetSum，它将字典格式转换为 sumTo 所需的输入，然后将结果转换回输出格式。这很容易修复以创建您需要的任何输出格式。

通过对输出进行一些格式化，我们可以更简单地查看结果：

subsetSum  (5, dict)
  .map (({initial, last}) => 
      Object .keys (initial) .join ('') +
      (last ? '-' + Object .keys (last) .join ('') : '')
  )
//=> ["abc-d", "abc-e", "abe", "ab-d", "acd", "ace-b", 
//    "ace-d", "ad-b", "ad-e", "ae-d", "bce", "bc-d", 
//    "bd", "be-d", "cd-b", "cd-e", "ce-d", "de"]

这可能表现不佳。我对问题的可能增长模式没有真正的了解。但是这个算法在字典的大小上是指数级的，并且对于这个技术没有办法绕过它，因为 partitions 核心的子集问题有 2 ^ n 个结果。

但这可能是与其他解决方案进行比较的起点。

原答案

如果所有顺序都很重要（我对该要求的细节感到困惑），那么这个算法应该这样做，使用一个条目列表，每个条目都有一个 key 和一个 value :

if (n <= 0) or if our list of entries is empty,
  return a list containing only the empty string
otherwise return the concatenation of the following lists, one for each entry:
  a recursive call passing 
    - `n - value`
    - the list excluding the current entry,
  with each result being prepended with the current entry's key

如果您熟悉 Javascript 语法，那么这应该可行：

const excluding = (i) => (xs) =>
  [...xs .slice (0, i), ...xs .slice (i + 1)]

const sumTo = (n, xs) =>
  n <= 0 || xs.length == 0 
    ? ['']
    : xs .flatMap (
        ([k, v], i) => sumTo (n - v, excluding (i) (xs)) .map (r => k + r)
      )
  
const subsetSum = (n, dict) => 
  sumTo (n, Object .entries (dict))

const dict = {a: 1, b: 2, c: 1, d: 3, e: 2}

console .log (subsetSum (5, dict))

.as-console-wrapper {max-height: 100% !important; top: 0}

很难想象顺序可能完全无关紧要，因为 'cde' 应该适合但 'dec' 不应该。但我不明白只有当总数超过目标时订单才有意义的概念。你能解释得更全面些吗？

等于或超过给定数字的所有组合

All combinations that equals or exceed a given number

algorithm

language-agnostic

combinations

subset-sum

更新答案

原答案