Является ли это неполиномиальной задачей? Если нет, то как ее решить за полиномиальное время?
Проблема:
Напишите функцию с двумя входными параметрами: items: список/вектор из двух кортежей положительных целых чисел (т.е. >= 1) target: положительное целое число (т.е. >= 1) Найдите подмножество кортежей, такое что: Сумма первых элементов кортежа подмножества больше или равна входу target. Сумма элементов второго кортежа подмножества минимальна, и назовем это значение суммы best. Функция должна просто вернуть best. Кроме того, гарантируется, что существует решение. Другими словами, сумма всех первых элементов кортежа всегда больше или равна цели. Вот сигнатура псевдокода такой функции: (items: List<(int, int)>, target: int) -> int И вот несколько примеров... Пример А: предметы = [(25,50), (49,51), (25,50), (1,100)] цель = 50 ответ = 100 Пример Б: предметы = [(25,50), (49,51), (25,50), (1,5)] цель = 50 ответ = 56
Вот мое наивное экспоненциальное решение:
- Пройдите через все возможные подмножества (следовательно, экспоненциальное время)
- Для каждого подмножества вычислите сумму первых элементов кортежа
- Если эта сумма больше или равна цели, то вычислите сумму вторых элементов кортежа
- Если эта новая сумма является наименьшей найденной до сих пор, обновите минимум
Я также попытался определить, есть ли математическое свойство проблемы, которое позволяет сократить путь, например. просмотрите элементы по наибольшему соотношению «первый элемент, деленный на второй элемент» (лучшая отдача). Однако, как показывает пример А, это справедливо не для всех случаев.
Является ли это неполиномиальной задачей? Если нет, то как ее решить за полиномиальное время?
Ответы 1
Это задача с рюкзаком 0-1: https://en.wikipedia.org/wiki/Knapsack_problem
Кортежи — это элементы, первые элементы кортежа — это значения элементов, вторые элементы кортежа — это веса элементов. Классический рюкзак спрашивает: «на best меньше определенного предела.
Таким образом, эта задача является NP-полной и не имеет решения за полиномиальное время.
Обычное решение для динамического программирования можно адаптировать для работы в O(items.length * best). Самый простой способ — использовать обычный метод DP, сначала с небольшим пределом наилучшего, а затем удваивая его, пока не будет достигнуто целевое значение.
Ну, нет известного решения за полиномиальное время.
Спасибо за упоминание проблемы с рюкзаком! Насколько я понимаю, он максимизирует сумму значений предметов в рюкзаке, чтобы сумма весов была меньше или равна вместимости. Моя проблема противоположна: минимизировать сумму весов предметов в рюкзаке так, чтобы сумма значений была больше или равна цели. Однако эта симметрия, вероятно, означает, что обе проблемы эквивалентны.
@MattTimmermans: я не уверен, что это проблема с рюкзаком 0-1. Вход items — это список, а не набор. Таким образом, каждый «предмет» может иметь разное максимальное количество копий. Например, в примере A элемент (25,50) может иметь две копии, а два других элемента могут иметь только одну копию. Но спасибо, что указали мне на проблему с рюкзаком, чтение об этом определенно поможет мне!
@FélixPoulin-Bélanger Различные части сайта относятся к этому по-разному. Люди, которые следуют [алгоритму], не возражают, но люди, которые следуют [python] и [производительности], вероятно, хотят больше практических вопросов. Эта задача слабо сложна — она похожа на задачу о рюкзаке, за исключением того, что вы решаете, какие предметы вынуть из рюкзака, чтобы соблюдать ограничение по весу, и пытаетесь максимизировать ценность, оставшуюся в рюкзаке.