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

All combinations that equals or exceed a given number

它不同于硬币兑换问题link

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

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

  1. 请注意,某些值是重复的,例如1和2各出现两次,需要分开考虑。
  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 时,顺序无关紧要,因为每个都得到它想要的任何东西,并且不会溢出到下一个槽。例如。 edde 意味着他们都得到了他们想要的,所以他们都应该被包括在内。 但是对于仅由于添加最后一个元素而超过 5 的列表,排序很重要,因为溢出只会发生在最后一个元素上。例如。 dce 表示 d 和 c 分别得到 3 和 1,而 e 只得到 1(1 溢出到下一个 运行)。类似地,ced 意味着 c 和 d 分别得到 1 和 3,d 发生溢出,因为它只被分配 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' 不应该。但我不明白只有当总数超过目标时订单才有意义的概念。你能解释得更全面些吗?