#algorithm #dynamic-programming
#алгоритм #динамическое программирование
Вопрос:
Я пытаюсь решить следующую задачу: учитывая набор предметов, каждый из которых имеет вес и значение, определите минимальную грузоподъемность рюкзака при заданном общем значении.
Например, ввод:
item1: w = 3.4, v = 3
item2: w = 0.4, v = 1
total value = 7
Вывод:
Мы должны взять:
item1 x0, item2 x7
И
minimal capacity = 0 * 3.4 0.4 * 7 = 2.8
total value = 7
Какие рекурсивные формулы я должен использовать для общего алгоритма с использованием динамического программирования? Может кто-нибудь показать пример решения этой проблемы с помощью крошечных входных данных?
PS Извините за мой английский.
Комментарии:
1. Это похоже на домашнюю задачу. Если это так, вы должны пометить его как таковой. Кроме того, вам нужно будет продемонстрировать некоторые усилия по решению этой проблемы. Пожалуйста, расскажите нам, какие подходы вы пробовали и с какими проблемами столкнулись.
2. @VaughnCato, я искал в Интернете формулы или примеры, но не нашел ничего, кроме «классической» проблемы с рюкзаком. Я знаю, что я должен минимизировать такую функцию, как F = Sum (Weighti * Counti) [i = 0 ..n](n — количество элементов) и F2 = сумма (значение * Количество) [i = 0 ..n] должно быть>=, чем total_value, но я не могу создавать формулы или алгоритм.
3. Что такое «минимальная грузоподъемность»? Почему это не просто не брать какие-либо предметы?
4. @отсутствует минимальная пропускная способность для заданного общего значения. Взяв некоторые элементы, мы должны получить или превысить общее значение
Ответ №1:
Традиционный (максимизирующий) алгоритм рюкзака должен работать нормально. Просто поменяйте местами все вхождения max for min , и вы должны быть почти там. Другой способ увидеть это — использовать отрицательные затраты, чтобы минимизация превратилась в максимизацию (однако вам нужно будет обратить особое внимание на пустой регистр).