不同的被加数问题 - 贪心算法 (Python)

Question

我正在尝试设计一个名为“distinct_summands”的函数，它接受一个正整数 n，输出一个包含 k 个不同整数 a1,...,ak 的列表，使得 a1+...+ ak= n 并且 k 尽可能大。

部分测试用例示例如下：distinct_summands(8)=[1,2,5], distinct_summands(2)=[2], distinct_summands (14)=[1, 2, 3, 8]。我自己测试了 n=1,2,3...,100K 的代码。到目前为止我没有发现任何错误。但是，当我将代码提交给黑盒代码测试器时，出现“超出索引”错误。

我尝试了我所知道的一切来找出问题所在。但我仍然不知道出了什么问题。我在下面附上了我的代码。谁能告诉我我做错了什么？

def distinct_summands(n):

    if n <=2: 
        return [n]
    
    remainder = n 

    number_list = list(range(1, n+1))

    prev_pos, curr_pos = 0, 0
    summands = []

    while remainder > number_list[prev_pos]:

        remainder = remainder - number_list[curr_pos]
        prev_pos = curr_pos
        summands.append(number_list[prev_pos])  
    
        if remainder >  2* number_list[curr_pos+1]:                     
            curr_pos += 1 
                
        else:

            curr_pos = remainder -1 
         
    return summands

Answer 1

如果 n 很大，那么 number_list = list(range(1, n+1)) 需要大量内存（可能是 out of index 错误的原因）。但是您使用 number_list 数组仅获取元素，所以我认为您可以将 number_list[index] 替换为 index + 1 并解决您的问题：


def distinct_summands(n):

    if n <= 2:
        return [n]

    remainder = n

    prev_pos, curr_pos = 0, 0
    summands = []

    while remainder > prev_pos + 1:

        remainder = remainder - (curr_pos + 1)
        prev_pos = curr_pos
        summands.append(prev_pos + 1)

        if remainder > 2 * (curr_pos + 2):
            curr_pos += 1
        else:
            curr_pos = remainder - 1

    return summands

不同的被加数问题 - 贪心算法 (Python)

Different Summands problem - greedy alogrithm (Python)

python

algorithm

greedy