超过Itertools.combinations()提升时间限制

Question

我正试图解决这个Python编码问题：

描述:老师安布罗西奥正在教他的女儿安布罗西妮塔二进制数字，所以他决定创建一个游戏。

安布罗西奥将给出N个数字给安布罗西尼塔，安布罗西妮塔可以从初始N中选择K个数字，对于所选的每一个数字，她的分数相当于1的分数，使用数字的二进制表示。

帮安布罗西尼塔找出她能挣多少分。

条目：

第一个输入行包含一个整数T，它指示测试用例的数量。

每个测试用例都从包含整数N(总数)和K(可以选择的数字)的一行开始。

每个情况的最后一个输入行包含N个整数，表示安布罗西尼塔可以选择的数字。

输出：

为每个测试用例打印一行，其中包含安布罗西尼塔能挣多少分。

1≤T≤10

1≤N≤10^3

0≤K≤N

0≤数≤10^5

执行时间限制为2秒。我得到一个TLE错误，但输出与预期相同。因此，输入必须有一定的长度。

这是我的密码：

import itertools

test_cases = int(input())

def binary(num):
    return format(num,'b')

def filter_string_1s(string):
    aux = ''
    for i in string:
        if i == '1':
            aux += i
    return aux

for i in range(test_cases):
    k = input().split()
    k = int(k[1])
    values = input().split()
    values = [int(i) for i in values]
    values = [filter_string_1s(str(binary(i))) for i in values]
    bin_values = []
    for combination in itertools.combinations(values,k):
        aux = 0
        for bin_number in combination:
            for i in bin_number:
                if i == '1':
                    aux += 1
        bin_values.append(aux)
    print(max(bin_values))

问:为了在执行期限内解决问题，我应该采取哪些步骤来优化它？

TLE =超过时限

Answer 1

这是一个"top-k“问题，而不是需要"k”组合的问题。为了阅读，让我们选择N= 990，K= 7。你需要在990的列表中选择前7名。

通过生成C(990，7) = 912,459,983,564,271,542,400组合，然后确定每个组合中的7个数字中有多少1位。这就是你没有时间的原因:你有990个数字需要考虑，但是你在重复输入中的每个数字的比特数。

少来这一套。你只需要看一遍这个列表，并保持前7位的数量。列表中的7个数字之间没有交互作用。事实上，你甚至不需要报告数字，仅仅是总分。

从一个包含7个零的列表开始。现在遍历所有990个数字。当您发现一个比列表中最小元素更大的位数时(为了便于引用，保持排序)，然后用新的分数替换它(并重新排序)。在所有990个数字的末尾，sum列表。

而且，数位比你做的要容易得多。将int转换为二进制字符串，并使用str.count(1)查看其中有多少1位。

Answer 2

她所能做的最大点将是选择拥有最多1位的K数。所以你只需要计算每个数字的点数，然后取上面的K。

例如：

import random

def maxPoints(K,N=None,numbers=None):
    numbers = numbers or [random.randrange(0,100001) for _ in range(N)]
    points  = sorted(bin(n).count("1") for n in numbers)
    return sum(points[-K:])

mp = maxPoints(3,numbers=[1,2,3,4,5])
print(mp) # 5

mp = maxPoints(1000,1000) 
print(mp) # will return instantly

Answer 3

解决了！谢谢大家。

代码：

test_cases = int(input())

for i in range(test_cases):
    k = input().split()
    k = int(k[1])
    nums = input().split()
    nums = [format(int(i),'b').count('1') for i in nums]
    nums.sort()
    sum = 0
    for i in range(k):
        sum += nums[-1]
        del nums[-1]
    print(sum)