在给定持续时间列表和上限的情况下查找唯一持续时间的数量

Question

假设我们得到了一个持续时间列表（5s、10s、10s、15s、15s、15s、25s、30s......），我们想要找到一个可以使用这个单一持续时间列表创建的唯一持续时间列表。持续时间。

例如，如果我们有 (5, 5, 15, 25) 的原始列表，我们可以创建以下持续时间：

• 5 - 使用一个 5 元素
• 10 - 使用两个 5 元素
• 15 - 使用一个 15 元素
• 20 - 使用 1 个 5 元件和 1 个 15 元件
• 25 - 使用两个 5 元素和一个 15 元素或使用 25 元素
• 30 - 使用 25 和 5
• 35 - 使用 25 和两个 5
• 40 - 使用 25 和 15
• 45 - 使用 25、15 和 5
• 50 - 使用所有元素

作为奖励，我想设定一个上限。例如，我想使用总持续时间 37 的上限。

这应该消除 40、45 和 50 的选项，因为它们超出了限制。

PS，原始列表中的持续时间非常频繁地重复，所以也许可以进行优化？

有人知道解决这个问题的方法吗？

我使用组合库来使用元素限制查找所有可能的组合，并消除超出最大限制的组合，但数量随着阶乘复杂性的增加而增长，这使得解决方案太慢。

Answer 1

您可以使用动态规划在

O(n * limit)

中解决此问题，其中

n

是列表中的元素数量，

limit

是上限。

例如，在Java中：

final int limit = 37;
final List<Integer> durations = List.of(5, 10, 10, 15, 15, 15, 25, 30);

var possible = new boolean[limit + 1];
// possible[i] indicates if it is possible to create the duration i
possible[0] = true; // base case

for (int duration : durations)
    for (int i = limit; i >= duration; i--)
        possible[i] |= possible[i - duration];

List<Integer> possibleDurations = new ArrayList<>();
for (int i = 1; i <= limit; i++)
    if (possible[i]) possibleDurations.add(i);

Answer 2

制作一个大小为

upper limit + 1

的表T，将1放入T[0]中，或者定义包含零值的集合。然后，对于每个值 v（持续时间），检查表中的非零条目（例如

i

）并将 1 放入

v+i

单元格中。

带有集合的Python示例：

a = [4,13,29]
lim = 37
t = {0}
for v in a:
    for i in range(lim - v + 1):
        if i in t:
            t.add(i + v)
t.remove(0)
print(t)

>> {4, 8, 12, 13, 16, 17, 20, 21, 24, 25, 26, 28, 29, 30, 32, 33, 34, 36, 37}