Найти минимальное количество элементов в списке, который охватывает определенные значения

Рекрутер хочет сформировать команду с разными навыками, и он хочет выбрать минимальное количество людей, которое может охватить все необходимые навыки.

N представляет количество людей, а K — количество различных навыков, которые необходимо включить. список spec_skill = [[1,3],[0,1,2],[0,2,4]] предоставляет информацию о навыках каждого человека. например у человека 0 есть навыки 1 and 3, у человека 1 есть навыки 0, 1 and 2 и так далее.

Код должен выводить размер наименьшей команды, которую смог найти рекрутер (минимальное количество людей), и значения, указывающие конкретные идентификаторы людей, которых нужно набрать в команду.

Я реализовал код с помощью грубой силы, как показано ниже, но, поскольку некоторые данные превышают тысячи, кажется, мне нужно решать с помощью эвристических подходов. В этом случае можно получить приблизительный ответ.

Любое предложение, как решить это с помощью эвристических методов, будет оценено.

N,K = 3,5
spec_skill = [[1,3],[0,1,2],[0,2,4]]

A = list(range(K))
set_a = set(A)

solved = False
for L in range(0, len(spec_skill)+1):
    for subset in itertools.combinations(spec_skill, L):
        s = set(item for sublist in subset for item in sublist)
        if set_a.issubset(s):
            print(str(len(subset)) + '\n' + ' '.join([str(spec_skill.index(item)) for item in subset]))
            solved = True
            break
    if solved: break

stackoverflow не является сайтом помощи в разработке кода, поэтому я думаю, что ваш вопрос не по теме.

martineau 09.12.2020 20:27

Нравится это?

superb rain 09.12.2020 20:29

Да, жадный алгоритм — один из возможных вариантов, но, похоже, ему нужно что-то более эффективное.

user14385051 09.12.2020 20:32

Который вы также можете найти на этой странице.

superb rain 09.12.2020 20:33

Подождите, что вы имеете в виду под "кажется, что нужно"? Говорит кто?

superb rain 09.12.2020 20:34

Это моя идея. Я пытаюсь изучить больше возможных подходов.

user14385051 09.12.2020 20:41

Является ли это NP-полной задачей вообще?

evenodd 09.12.2020 20:49

@evenodd, Да, это так.

user14385051 09.12.2020 20:50
Почему в Python есть оператор "pass"?
Почему в Python есть оператор "pass"?
Оператор pass в Python - это простая концепция, которую могут быстро освоить даже новички без опыта программирования.
Некоторые методы, о которых вы не знали, что они существуют в Python
Некоторые методы, о которых вы не знали, что они существуют в Python
Python - самый известный и самый простой в изучении язык в наши дни. Имея широкий спектр применения в области машинного обучения, Data Science,...
Основы Python Часть I
Основы Python Часть I
Вы когда-нибудь задумывались, почему в программах на Python вы видите приведенный ниже код?
LeetCode - 1579. Удаление максимального числа ребер для сохранения полной проходимости графа
LeetCode - 1579. Удаление максимального числа ребер для сохранения полной проходимости графа
Алиса и Боб имеют неориентированный граф из n узлов и трех типов ребер:
Оптимизация кода с помощью тернарного оператора Python
Оптимизация кода с помощью тернарного оператора Python
И последнее, что мы хотели бы показать вам, прежде чем двигаться дальше, это
Советы по эффективной веб-разработке с помощью Python
Советы по эффективной веб-разработке с помощью Python
Как веб-разработчик, Python может стать мощным инструментом для создания эффективных и масштабируемых веб-приложений.
2
8
450
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Вот мой способ сделать это. В коде могут быть потенциальные возможности оптимизации, но основная идея должна быть понятной.

import random
import time
def man_power(lst, K, iterations=None, period=0):
    """
    Specify a fixed number of iterations
    or a period in seconds to limit the total computation time.
    """

    # mapping each sublist into a (sublist, original_index) tuple
    lst2 = [(lst[i], i) for i in range(len(lst))]
    mini_sample = [0]*(len(lst)+1)
    if period<0 or (period == 0 and iterations is None):
        raise AttributeError("You must specify iterations or a positive period")
    
            
    def shuffle_and_pick(lst, iterations):
        mini = [0]*len(lst)
        for _ in range(iterations):
            random.shuffle(lst2)
            skillset = set()
            chosen_ones = []
            idx = 0
            fullset = True
            # Breaks from the loop when all skillsets are found
            while len(skillset) < K:
                # No need to go further, we didn't find a better combination
                if len(chosen_ones) >= len(mini):
                    fullset = False
                    break
                before = len(skillset)
                skillset.update(lst2[idx][0])
                after = len(skillset)
                if after > before:
                    # We append with the orginal index of the sublist
                    chosen_ones.append(lst2[idx][1])
                idx += 1
            if fullset:
                mini = chosen_ones.copy()
        return mini
    
    # Estimates how many iterations we can do in the specified period
    if iterations is None:
        t0 = time.perf_counter()
        mini_sample = shuffle_and_pick(lst, 1)
        iterations = int(period / (time.perf_counter() - t0)) - 1
    
    mini_result = shuffle_and_pick(lst, iterations)
    if len(mini_sample)<len(mini_result):
        return mini_sample, len(mini_sample)
    else:
        return mini_result, len(mini_result)

@ Whole Brain, хороший подход. Можно ли сделать его более оптимизированным, так как все еще не может передавать очень большие входные данные?

user14385051 11.12.2020 00:21

Другие вопросы по теме