Номер группы: 11-104

Фамилия и Имя: Камалов Нияз

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

Подходы к реализации полного перебора:

• bit-masking - характеристический вектор или битовая маска, описывающая отсутствие (0) или вхождение (1) элементов в рассматриваемое подмножество. Представляет собой итеративный проход по всем возможным решениям.
• backtracking - поиск с возвратом. Используется рекурсия для рассмотрения и отсечения (возврат) непригодных решений.

Требуется реализовать генерацию всех возможных подмножеств некого множества.

  Множество S = {1, 3}
  Подмножества: {}, {1}, {3}, {1, 3}

Дополнительно:

• подумайте, как реализовать наложение дополнительных ограничений к задаче (при S = {1, 2, 3, 4})
  • мощность подмножества не более 3
  • в подмножестве не должен встречаться элемент 2
  • вывести только те подмножества, в которых обязательно есть элементы 2 и 4

Требуется реализовать поиск всех возможных подмножеств множества, сумма элементов которых равна целевой сумме (T).

Множество S = {1, 3, 2, 5, 10}
Целевая сумма T = 5

Подмножества: {3, 2}, {5}

Дополнительно:

• подумайте, как реализовать поиск всех подмножеств, сумма элементов которых наиболее близка к целевой сумме (T)

Является опциональной задачей на доп. баллы.

С описанием задачи можно ознакомиться по ссылке.

1. Склонируйте локальную копию репозитория к себе на компьютер.
2. Внесите информацию о себе в раздел "Информация о студенте".
3. Подробно изучите описание задания. При наличии вопросов обратитесь к врачу преподавателю.
4. Реализуйте задание в соответствии указанным требованиям.
5. Запустите локальные тесты (при их наличии).
6. Отправьте задание на auto-grading тесты и дождитесь итогового балла.
7. Повторите пункты 4-6 до получения макс. кол-ва баллов.

• Запрещается вносить изменения в файлы, не указанных в разделе "Описание задания".
• Запуск auto-grading тестов осуществляется:
  • автоматически при внесении изменений в src и/или include на ветках master или main;
  • вручную во вкладке Actions.

• Результирующие баллы высчитываются при каждом новом push'е (для последнего commit'а).
• По истечении установленных временных сроков сдачи система продолжит высчитывать итоговый балл при внесении изменений.
• Сроки сдачи устанавливаются преподавателем и указываются в индивидуальном порядке для каждой группы.
• Тесты подразделяются на локальные и auto-grading:
  • локальные тесты запускаются на компьютере через среду разработки (IDE);
  • auto-grading тесты запускаются на GitHub и вычисляют итоговый балл за задание.
• При клонировании репозитория через терминал используйте команду:

    git clone --recurse-submodules <URL>

Преподаватель: Рамиль Сафин (Telegram: @safin_ramil, e-mail: safin.ramil@it.kfu.ru).