Рекрутер хочет сформировать команду с разными навыками, и он хочет выбрать минимальное количество людей, которое может охватить все необходимые навыки.
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
Нравится это?
Да, жадный алгоритм — один из возможных вариантов, но, похоже, ему нужно что-то более эффективное.
Который вы также можете найти на этой странице.
Подождите, что вы имеете в виду под "кажется, что нужно"? Говорит кто?
Это моя идея. Я пытаюсь изучить больше возможных подходов.
Является ли это NP-полной задачей вообще?
@evenodd, Да, это так.
Вот мой способ сделать это. В коде могут быть потенциальные возможности оптимизации, но основная идея должна быть понятной.
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, хороший подход. Можно ли сделать его более оптимизированным, так как все еще не может передавать очень большие входные данные?
stackoverflow не является сайтом помощи в разработке кода, поэтому я думаю, что ваш вопрос не по теме.