Проблема с ограничениями не обрабатывает некоторые тестовые случаи
У меня есть такая проблема с ограничениями Python: вам нужно составить график представления докладов на конференции. Всего на конференции будет представлено 10 докладов из нескольких областей: искусственный интеллект (ИИ), машинное обучение (ML) и обработка естественного языка (NLP). Ваша задача – составить расписание конференции по датам с учетом следующих ограничений: В каждом семестре можно представить максимум 4 доклада. Если количество статей из данной области меньше или равно максимальному количеству статей, которое может быть представлено в течение данного семестра, то эти статьи должны быть распространены в том же семестре. И у меня есть этот код:
from constraint import *
def domain_length(domain):
return len(domain) < 4
if __name__ == '__main__':
num_terms = int(input())
papers = dict()
paper_info = input()
while paper_info != 'end':
title, topic = paper_info.split(' ')
papers[title] = topic
paper_info = input()
# Define variables
variables = list(papers.keys())
domain = [f'T{i + 1}' for i in range(num_terms)]
problem = Problem(BacktrackingSolver())
# Add variables to problem
problem.addVariables(variables, domain)
# Add constraints
for area in ['AI', 'ML', 'NLP']:
area_papers = [title for title, topic in papers.items() if topic == area]
area_num_papers = len(area_papers)
if area_num_papers <= 4:
# If there are fewer papers than the number of terms, assign them to different terms
problem.addConstraint(AllEqualConstraint(), area_papers)
else:
# Otherwise, assign papers to non-overlapping sets of terms
papers_sets = [area_papers[i:i + 4] for i in range(0, area_num_papers, 4)]
for papers_set in papers_sets:
# Add constraints to ensure each set is assigned to a different term
problem.addConstraint(AllDifferentConstraint(), papers_set)
# Add constraints to ensure no more than 4 papers are assigned to each term
for term in domain:
problem.addConstraint(lambda *papers, t=term: sum(1 for p in papers if p == t) <= 4, papers_set)
# Add constraint for maximum of 4 papers per term
for term in domain:
problem.addConstraint(lambda *papers, t=term: sum(1 for p in papers if p == t) <= 4, variables)
result = problem.getSolution()
# Print solution
for paper, term in result.items():
print(f"{paper} ({papers[paper]}): {term}")
Код работает корректно, если по теме не более 4 статей. Теперь проблема в том, что код не находит решения, если по определенной теме имеется более 4 статей. Например, если имеется 6 статей AI, он не печатает решения там, где должно. Строка, которая обрабатывает эти случаи:
papers_sets = [area_papers[i:i + 4] for i in range(0, area_num_papers, 4)]
Правильно разделяет документы, как в примере вывода, но тогда я думаю, что есть проблема с ограничением:
for papers_set in papers_sets:
# Add constraints to ensure each set is assigned to a different term
problem.addConstraint(AllDifferentConstraint(), papers_set)
потому что не находит решения. В чем может быть проблема? Вот пример ввода и вывода:
Input:
3
Paper1 AI
Paper2 AI
Paper3 AI
Paper4 AI
Paper5 NLP
Paper6 AI
Paper7 NLP
Paper8 NLP
Paper9 NLP
Paper10 NLP
end
Output:
Paper1 (AI): T3
Paper2 (AI): T3
Paper3 (AI): T3
Paper4 (AI): T2
Paper5 (NLP): T2
Paper6 (AI): T2
Paper7 (NLP): T2
Paper8 (NLP): T1
Paper9 (NLP): T1
Paper10 (NLP): T3