Математика EN

Тренажёры · Глава 60

Сумма подмножества

Выберите из набора числа с заданной суммой. Проверить ответ — секунда, а найти его — перебор: на этой задаче видно, чем P отличается от NP.

Как решать

Задача о сумме подмножества: даны числа и цель, нужно выбрать несколько чисел с суммой, равной цели. Проверить предложенный ответ легко — сложить. А вот найти его быстрее, чем перебором, неизвестно как: у $n$ чисел $2^n$ подмножеств. Это одна из NP-полных задач — главных героев вопроса «P = NP?».

По шагам

  1. Упорядочьте числа по убыванию: крупные числа быстрее приближают к цели.
  2. Берите числа по очереди, пока сумма не превышает цель. Если зашли в тупик — уберите последнее взятое и попробуйте следующее (перебор с возвратом).
  3. Отсекайте безнадёжные ветки: если даже все оставшиеся числа не добирают до цели, дальше идти незачем.
  4. Помогает чётность и последняя цифра: например, чтобы получить нечётную сумму, нужно нечётное количество нечётных чисел.
  5. Проверьте ответ сложением.
Сколько чисел в наборе: каждое либо берём, либо нет. Пример: из $\{29, 31, 17, 33, 12\}$ сумма $48$: $31 + 17 = 48$. Проверка — одно сложение, а вариантов было $2^5 = 32$.

Где ошибаются

  • Берут одно число дважды — каждое можно использовать не больше одного раза.
  • Жадно берут самые большие числа и не возвращаются, когда сумма перевалила за цель.
  • Думают, что ответ единственный. Подходящих наборов может быть несколько — засчитывается любой.
  • Не проверяют сумму в конце — арифметическая ошибка обидна именно здесь.

Пример

Математика

Главы курса

Вступление

  1. 0 Что такое математика

I Числа

  1. 1 Счёт
  2. 2 Ноль и минус
  3. 3 Простые числа
  4. 4 Делимость
  5. 5 Дроби
  6. 6 Корень из двух

II Алгебра

  1. 7 Буквы
  2. 8 Уравнения
  3. 9 Функции и графики
  4. 10 Квадратные уравнения
  5. 11 Системы и неравенства
  6. 12 Степени и логарифмы
  7. 13 Последовательности
  8. 14 Многочлены
  9. 15 Комплексные числа

III Геометрия

  1. 16 Начала Евклида
  2. 17 Треугольник
  3. 18 Теорема Пифагора
  4. 19 Окружность и π
  5. 20 Площадь и объём
  6. 21 Тригонометрия
  7. 22 Векторы
  8. 23 Симметрия
  9. 24 Конические сечения

IV Анализ

  1. 25 Пределы
  2. 26 Производная
  3. 27 Экстремумы
  4. 28 Интеграл
  5. 29 Число e
  6. 30 Ряды
  7. 31 Дифференциальные уравнения
  8. 32 Многие переменные
  9. 33 Ряды Фурье
  10. 34 Комплексный анализ

V Линейная алгебра

  1. 35 Матрицы
  2. 36 Метод Гаусса
  3. 37 Векторные пространства
  4. 38 Собственные векторы
  5. 39 МНК и SVD

VI Структуры

  1. 40 Группы
  2. 41 Остатки и шифры
  3. 42 Кольца и поля
  4. 43 Теория Галуа
  5. 44 Дзета и кривые

VII Случай и данные

  1. 45 Комбинаторика
  2. 46 Графы
  3. 47 Вероятность
  4. 48 Случайные величины
  5. 49 Статистика
  6. 50 Марков и информация

VIII Основания

  1. 51 Логика и множества
  2. 52 Бесконечности
  3. 53 Строгий анализ
  4. 54 Мера и интеграл
  5. 55 Функциональный анализ
  6. 56 Гёдель и Тьюринг

IX Горизонты

  1. 57 Топология
  2. 58 Неевклидовы геометрии
  3. 59 Хаос и фракталы
  4. 60 Передний край