Itertools.combination () поднял превышение лимита времени

Question

Я пытаюсь решить эту проблему кодирования Python:

Описание: Учитель Амброзио обучает двоичные числа своей дочери Амбросините, поэтому он решил создать игру.

Амброзио даст N чисел Амброзините, который может выбрать K чисел среди начальных N. За каждое выбранное число она зарабатывает балл, эквивалентный числу 1, используя двоичное представление числа.

Помогите Амбросините чтобы узнать, сколько очков она может заработать.

Запись:

Первая строка ввода содержит целое число T, которое указывает количество тестовых случаев.

Каждый тестовый случай начинается со строкой, содержащей целые числа N (общее число) и K (числа, которые можно выбрать).

Последняя строка ввода каждого случая содержит N целых чисел, представляющих числа, которые может выбрать Амброзинита.

Вывод:

Для каждого теста выведите строку, содержащую количество очков, которое Амброзинита может заработать.

1 ≤ T ≤ 10

1 N ≤ 10 ^ 3 * * * тысяча двадцать-пять * 0 тысячи двадцать-шести ≤ K ≤ N * * * тысяча двадцать-семь +1028 * 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. Вам нужно выбрать 7 лучших баллов в списке из 990.

Вы сделали это, сгенерировав C (990, 7) = 912,459,983,564,271,542,400 комбинации , затем определяют, сколько 1 битов в каждом из 7 чисел в каждой комбинации. Вот почему у вас заканчивается время: у вас есть 990 чисел, которые нужно учитывать, но вы повторяете количество раз в миллионы раз для каждого числа на входе.

Сбейте его. Все, что вам нужно, - это go просмотреть этот список один раз и сохранить верхние 7-битные значения. Нет взаимодействия между 7 числами в списке. На самом деле вам даже не нужно сообщать о цифрах, а просто общую оценку.

Начните со списка из семи нулей. Теперь переберите все 990 номеров. Каждый раз, когда вы находите число битов больше, чем наименьший элемент списка (сохраняйте его отсортированным для удобства пользования), затем заменяйте его новым счетом (и пересортируйте). В конце всех 990 чисел, sum список.

Также считать биты намного проще, чем вы. Преобразуйте int в двоичную строку и используйте str.count(1), чтобы увидеть, сколько в ней 1 битов.

Answer 2

Решено! Спасибо всем.

Код:

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)

Answer 3

Максимальное количество баллов, которое она может получить, выбрав число К, которые имеют максимум 1 бит. Так что вам просто нужно вычислить баллы для каждого числа и взять верхнюю 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