等于或超过给定数字的所有组合
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和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.
更新答案
有关要求的更多详细信息已添加到问题中。我认为这个版本适合他们。但是没有指定预期的输出结构,所以这是一个猜测。它以这样的结果数组结尾:
{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'
不应该。但我不明白只有当总数超过目标时订单才有意义的概念。你能解释得更全面些吗?
它不同于硬币兑换问题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.
更新答案
有关要求的更多详细信息已添加到问题中。我认为这个版本适合他们。但是没有指定预期的输出结构,所以这是一个猜测。它以这样的结果数组结尾:
{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'
不应该。但我不明白只有当总数超过目标时订单才有意义的概念。你能解释得更全面些吗?