提升算法效率的策略？

1 投票

2 回答

105 浏览

数据工程师

提问于 2025-04-12 22:49

我有一个任务：

安娜妈妈打开了一包糖果，她想把这些糖果分给她的孩子们作为奖励。为了避免他们之间发生争执，当然，比赛中表现好的孩子不能得到比表现差的孩子少的糖果。那么，安娜可以把C颗糖果分给D个孩子的方式有多少种呢？

任务：
给定数字D和C，找出糖果的可能分配方式的数量。

输入：
文件的第一行有一个数字Q，表示数据组的数量。接下来有Q行，每行包含一对数字D和C。

1 ≤ Q ≤ 1000
1 ≤ D ≤ 100
1 ≤ C ≤ 5,000

输出：
程序的输出是每组数据的结果，结果需要对(2^30)-1取模，并且每个结果单独一行。

示例
输入：

输出：

1
3
10

我写了这个代码，它能工作，但当我有1000个输入时，评估器给我**超时**的错误，你能帮我写一个更快的代码吗？

def generate_combinations(d, c, current_combination=None, combinations=None):
    if current_combination is None:
        current_combination = []

    if combinations is None:
        combinations = []

    if d == 0:
        if c == 0:
            if all(current_combination[i] <= current_combination[i + 1] for i in range(len(current_combination) - 1)):
                
                combinations.append(list(current_combination))
        return

    for i in range(c + 1):
        generate_combinations(d - 1, c - i, current_combination + [i], combinations)

    return combinations

c = 8  
d = 3 

pocet = int(input())
for i in range(pocet):
    d, c = map(int, input().split())
    print(len(generate_combinations(d, c)))

我还有一个使用动态规划的版本。

def dynamic_programming(d, c):
    dp = [[0] * (c + 1) for _ in range(d + 1)]
    dp[0][0] = 1

    for i in range(1, d + 1):
        for j in range(c + 1):
            dp[i][j] = dp[i - 1][j]
            if j >= i:
                dp[i][j] += dp[i][j - i]
            dp[i][j] %= (2 ** 30 - 1)
    b = dp[d][c]
    return dp[d][c]

q = int(input().strip())

for i in range(q):
    d, c = map(int, input().split())
    print(dynamic_programming(d, c))

为了更好地理解，这里有一个例子：如果我们想把8颗糖果分给3个孩子，我们有21种可能性：

[0, 0, 8]
[0, 1, 7]
[0, 2, 6]
[0, 3, 5]
[0, 4, 4]
[0, 5, 3]
[0, 6, 2]
[0, 7, 1]
[0, 8, 0]
[1, 0, 7]
[1, 1, 6]
[1, 2, 5]
[1, 3, 4]
[1, 4, 3]
[1, 5, 2]
[1, 6, 1]
[1, 7, 0]
[2, 0, 6]
[2, 1, 5]
[2, 2, 4]
[2, 3, 3]
[2, 4, 2]
[2, 5, 1]
[2, 6, 0]
[3, 0, 5]
[3, 1, 4]
[3, 2, 3]
[3, 3, 2]
[3, 4, 1]
[3, 5, 0]
[4, 0, 4]
[4, 1, 3]
[4, 2, 2]
[4, 3, 1]
[4, 4, 0]
[5, 0, 3]
[5, 1, 2]
[5, 2, 1]
[5, 3, 0]
[6, 0, 2]
[6, 1, 1]
[6, 2, 0]
[7, 0, 1]
[7, 1, 0]
[8, 0, 0]

而且只有10种可能性符合这个任务的要求：

[0, 0, 8]
[0, 1, 7]
[0, 2, 6]
[0, 3, 5]
[0, 4, 4]
[1, 1, 6]
[1, 2, 5]
[1, 3, 4]
[2, 2, 4]
[2, 3, 3]

数据结构模运算复杂度分析算法效率组合数学动态规划分配问题递归优化

2 个回答

如果你只是想计算有效组合的数量，可以使用这段代码，它会先把糖果分给“最优秀”的孩子，然后把剩下的糖果递归地分给其他孩子。这段代码的效率应该比你的高，因为它只关注可能有效的组合，并且会缓存之前计算过的结果：

from functools import cache

@cache
def distribute_candies(C, Q, last_C = None):
    if C == 0:
        # can only distribute 0 as [0] * Q
        return 1
    if Q == 1:
        # they get them all
        return 1
    # maximum number of candies the "best" person can have is C, 
    # or as many as the last person had if that is less
    # minimum number (which still allows distribution) is (C + Q - 1) // Q
    maxc = min(C, last_C if last_C else C)
    minc = (C + Q - 1) // Q
    valid = 0
    for c in range(maxc, minc-1, -1):
        valid += distribute_candies(C - c, Q - 1, c)
    return valid

distribute_candies(4, 2)
# 3
distribute_candies(8, 3)
# 10

如果你对实际的组合感兴趣，可以使用这段代码（然后只需用len来获取组合的数量），不过要注意，对于大输入，这段代码会很快耗尽内存，因为组合的数量会非常庞大：

from functools import cache

@cache
def distribute_candies(C, Q, last_C = None):
    if Q == 1:
        # they get them all
        return [[C]]
    # maximum number of candies the "best" person can have is C, 
    # or as many as the last person had if that is less
    # minimum number (which still allows distribution) is (C + Q - 1) // Q
    maxc = min(C, last_C if last_C else C)
    minc = (C + Q - 1) // Q
    dist_C = []
    for c in range(maxc, minc-1, -1):
        dist_C += [l + [c] for l in distribute_candies(C - c, Q - 1, c)]
    return dist_C

distribute_candies(4, 2)
# [[0, 4], [1, 3], [2, 2]]
distribute_candies(8, 3)
# [[0, 0, 8], [0, 1, 7], [0, 2, 6], [1, 1, 6], [0, 3, 5], [1, 2, 5], [0, 4, 4], [1, 3, 4], [2, 2, 4], [2, 3, 3]]

回答于 2025-04-12 由 Python大师

分享举报

想象一下，把糖果分配给孩子们的每一种方式，其实就是把 n 颗糖果分成 k 份。需要注意的是，对于每一种分配方式，只有一种合法的分配给孩子们的方式（比如说，当 n=7 时，分配方式 3 3 1 只能对应到孩子们的分配 [0, 3, 3]，其他的分配方式都是不合法的）。

所以，我们只需要计算出 n 颗糖果的 k 份分配的数量，这里有一个很好的递归公式：

p(0, 0) = 1
p(n, k) = 0  if n <= 0 or k <= 0
p(n, k) = p(n - k, k) + p(n - 1, k - 1)

不过，我们需要小心，这个公式计算的是非空的分配，但我们允许给孩子 0 颗糖果。我们可以修改递归关系，但其实有个更简单的方法：在开始的时候，每个孩子先加 1 颗糖果，然后再想象把这颗糖果从他们的分配中拿掉，这样就好像我们允许空的分配了。

下面是用 Python 实现的：

from functools import cache

@cache
def count_parts(candies, children):
    if candies == children == 0:
        return 1
    if candies <= 0 or children <= 0:
        return 0
    return count_parts(candies - children, children) + count_parts(candies - 1, children - 1)

示例用法：

test_cases = [(10, 1), (4, 2), (8, 3)]
for candies, children in test_cases:
    print(count_parts(candies + children, children))

输出结果：

1
3
10

这个方法的时间和空间复杂度都是 O(C*D)，而用自底向上的动态规划方法，虽然时间复杂度相同，但在实际操作中会稍微快一些，并且可以做到线性的空间复杂度（相对于 C）。

具体的细节我现在记不太清了，但我相信还有一种早期退出的快捷计算方法可以用来计算 p(2*k, k)，这样也能进一步加快速度。

回答于 2025-04-12 由 Python大师

分享举报

提升算法效率的策略？

2 个回答

撰写回答