0
1

Дано множество положительных целых чисел S и целое число t. Спрашивается, существует ли подмножество T $%\subseteq$% S, такое что сумма чисел в T равна t?

Предложите алгоритм решения этой задачи, сложность которого не превышает $%2^{\frac{l}{2}}poly(l)$%, где $%l = |S|$% и $%poly(l)$% — некоторый многочлен, зависящий от $%l$%.

задан 8 Окт '19 20:30

10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

регистрация »

отмечен:

×214
×131
×55

задан
8 Окт '19 20:30

показан
110 раз

обновлен
8 Окт '19 20:30

Связанные вопросы

0 Оценить число рекурсивных вызовов процедуры

0 Построить алгоритм, который по $%A[1…n]$% выводит его мин. $%\sqrt{n}$% элементов по возрастанию

0 Задача на амортизационный анализ

0 Какую функцию вычисляет программа [закрыт]

0 Постройте как можно более быстрый алгоритм

0 Курс вычислимость и сложность

0 Минимизация расстояния Левенштейна

0 Найти Theta-асимптотику и вычислить функцию

1 Срочно нужна помощь в теории алгоритмов (про 2-КНФ, n-КНФ и SAT)

-1 Докажите, что TIME(2^n) является собственным подмножеством TIME(2^2n)

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru