Максимальное количество тестов, которые могут быть сформированы с учетом условий

Question

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

ВВОД:

• Каждый вопрос относится к любой из 3 категорий , а именно JAVA, PYTHON и MYSQL
• Каждый вопрос относится к любому из двух уровней сложности. EASY и DIFFICULT

ПРАВИЛА, КОТОРЫЕ ВОПРОС ДОЛЖЕН Удовлетворять:

• В каждой категории должно быть не менее 1 вопроса (java | python | mysql).

• не менее 2 вопросов из каждый уровень сложности.

• Тест должен содержать ровно 5 вопросов. (Позволяет позвонить по этому номеру K )

• Вопрос, однажды добавленный в тест, не может повторяться ни в одном другом тесте.

Я попробовал наивный способ со следующей стратегией:

• Форма н / к групп.

• Если есть 15 вопросов и k = 4, мы можем сформировать не более 15/4 = 3 тестов (групп).

• Для в каждой группе, перебирайте вопросы и добавляйте их в эту группу, если она удовлетворяет условиям.

• Если вопрос добавлен, уменьшите требования к сложности теста и требования к категории

Как только у нас будут группы с минимальными условиями, выполните итерации по оставшимся вопросам и добавьте их в тесты, чтобы тест содержал K вопросов.

Проблема с этим Это работает, только если входные вопросы находятся в определенном c благоприятном порядке. Я запустил программу со случайными перемешанными входными вопросами. Я получил разные выводы. ( Я могу поделиться кодом, если требуется )

Итак, как я понял, вышеприведенное решение не является надежным. Мы должны тщательно проверить все комбинации вопросов. Казалось, что это очень похоже на Минимальная проблема с монетами .

Это отличается от MCC следующими способами

1. Количество монет ограничено. {1,1,2,2,2,3,4,5}
2. Нам нужно не количество монет, а группа монет, удовлетворяющих некоторым условиям.
3. Развернуть. не минимизировать.
4. Максимизировать количество групп (не монет), которые удовлетворяют заданным условиям.

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

Как я могу решить эту проблему с помощью DP? Как я могу получить рекуррентное отношение для этой проблемы? Пожалуйста, начните с рекурсивного решения, если это возможно

Answer 1

Идея, основанная на кликах :

, учитывает N действительных тестов (N < C_n^5). Мы хотим сделать семейство тестов (максимально возможное) таким, чтобы его тесты не пересекались: у них нет общих вопросов.

• Скажем, тест - это узел (графа G)
• Викторина связана с другой викториной, если НЕТ общего вопроса: существует грань.
• Создайте максимальную клику G.

Если вам нужно написать это от руки, рассмотрите следующее al go для максимальной клики:

function buildClique(clique, nodes)
  if nodes.empty
    return clique

  n = nodes[0]
  if clique + n is not a clique
    return buildClique(clique, nodes - n)

  return max( //consider returning the clique which is the biggest
    buildClique(clique + n, nodes - n) // add the node to the clique
    buildClique(clique, nodes - n) // do not add it
  )

Вы бы взяли самую большую клику, построив самую большую клику из каждого узла

bestClique = []
forall nodes as n
  clique = buildClique([n], nodes - n)
  if size(clique) > size(bestClique)
    bestClique = clique

DP (если указать, что максимальная клика состоит из клик меньшего размера), мы можем

• построить все клики размером 1,
• построить их размером 2 путем добавления «совместимого» узла к каждой клике размером 1
• и т. д.
• до тех пор, пока не будет клики размера m: мы можем взять любую клику размером m-1