Уровень: ★☆☆☆☆
Теги: "алгоритм" "DP стратегия" "динамическое программирование"
автор:MrLiuQ
Рассмотрение:Команда QiShare
Эта статья познакомит вас со знаниями динамического программирования.
1. Введение
Динамическое программирование (Dynamic Programming, именуемое DP).
этоГлавная мысльЭто разделить большую сложную проблему на несколько подзадач и решить их путем решенияподзадачарешать постепеннобольшая проблема.
Примечание. Необходимое условие для использования идей динамического программирования:Динамическое программирование можно использовать тогда и только тогда, когда каждая подзадача дискретна (т. е. каждая подзадача не зависит от других подзадач).
2. «Проблема рюкзака 0-1» динамического программирования.
Сейчас такая сцена, «Ты» — «вор», ты несешь сумку, чтобы «украсть вещи».
Условие 1: На каждый предмет приходится только один предмет, либо брать, либо нет. (0-1 задача с рюкзаком)
Условие 2: Вы можете больше двигаться4kgс вещами. (фиксированный размер, не полный)
| товар | цена | масса |
|---|---|---|
| Товар А | 3000 юаней | 4kg |
| Товар Б | 2000 долларов | 3kg |
| Товар С | 1500 юаней | 1kg |
| Товар Д | 2000 долларов | 1kg |
существуетограниченный весКак в этих условиях «украсть» и заработать больше денег?
Вариант 1: Простой алгоритм (возможный, но не рекомендуемый)
Яростно перечисляет перестановки и комбинации всех товаров, бросить всеПревышает требования по весуКомбинация, Выберите самый крупный из них.
Это работает, но слишком медленно, с в 2 раза больше комбинаций для каждого дополнительного элемента.
Оценка схемы: временная сложность O(2n), супер супер медленный, не рекомендуется.
Вариант 2: жадный алгоритм (нереализуемый)
используя предыдущийкак деларассчитать.
Приближенное решение получается с помощью жадной стратегии (брать самый дорогой и самый рентабельный товар).
Оценка схемы: Эта схема близка к оптимальному решению и является приближенным решением, но это не обязательно оптимальное решение, поэтому она не реализуема.
Вариант 3: Динамическое программирование (выполнимо, рекомендуется)
- Принцип: сначала решитьдополнительный рюкзаклучше, а потом решайбольшой рюкзакоптимальный.
Сначала нарисуйте таблицу, и через некоторое время мы будем заполнять ее столбец за столбцом. (PS: испытайте алгоритмический процесс динамического программирования)
Таблица: (фактически соответствует двумерному массиву)
| Максимальный вес товарного\суб-рюкзака | 1kg | 2kg | 3kg | 4kg |
|---|---|---|---|---|
| Товар А | ||||
| Товар Б | ||||
| Товар С | ||||
| Товар Д |
Сначала прочтите эту таблицу.
Строка: представляет товарную строку (соответствуетi),
Столбец: представляет столбец веса (соответствуетj),
Сетка: представляет текущие существующие товары, количество, которое можно взять под существующим весом.максимальное значение.
Что ж, начнем заполнять столбец за столбцом:
Первая строка, только товар А (стоимость: 3000, вес: 4кг)
| Максимальный вес товарного\суб-рюкзака | 1kg | 2kg | 3kg | 4kg |
|---|---|---|---|---|
| Товар А | / | |||
| Товар Б | ||||
| Товар С | ||||
| Товар Д |
Во втором ряду есть товар А (стоимость: 3000, вес: 4 кг) и товар Б (стоимость: 2000, вес: 3 кг).
| Максимальный вес товарного\суб-рюкзака | 1kg | 2kg | 3kg | 4kg |
|---|---|---|---|---|
| Товар А | / | |||
| Товар Б | / | |||
| Товар С | ||||
| Товар Д |
В третьем ряду находятся товар А (стоимость: 3000, вес: 4 кг), товар В (стоимость: 2000, вес: 3 кг) товар С (стоимость: 1500, вес: 1 кг)
| Максимальный вес товарного\суб-рюкзака | 1kg | 2kg | 3kg | 4kg |
|---|---|---|---|---|
| Товар А | / | |||
| Товар Б | / | |||
| Товар С | 1500 | |||
| Товар Д |
В четвертом ряду находятся товар A (стоимость: 3000, вес: 4 кг), товар B (стоимость: 2000, вес: 3 кг), товар C (стоимость: 1500, вес: 1 кг), товар D (стоимость: 2000, вес: 1 кг). вес: 1 кг)
| Максимальный вес товарного\суб-рюкзака | 1kg | 2kg | 3kg | 4kg |
|---|---|---|---|---|
| Товар А | / | |||
| Товар Б | / | |||
| Товар С | 1500 | |||
| Товар Д | 2000 |
Вы заметили, что алгоритм заполнения каждой формы здесь можно выразить так:
Если вес товара в соответствующей строке превышает вес текущего субрюкзака, берется значение ячейки в предыдущей строке.
Если вес продукта может соответствовать текущему дополнительному рюкзаку, возьмите большее из следующих двух значений:
- значение предыдущей ячейки (
cell[i-1][j])- Значение текущего элемента + значение оставшегося места (
cell[i-1][j-当前商品的重量所对应的列号])
Заполните вторую колонку ниже:
| Максимальный вес товарного\суб-рюкзака | 1kg | 2kg | 3kg | 4kg |
|---|---|---|---|---|
| Товар А | / | / | ||
| Товар Б | / | / | ||
| Товар С | 1500 | 1500 | ||
| Товар Д | 2000 | 3500 |
Третий столбец:
| Максимальный вес товарного\суб-рюкзака | 1kg | 2kg | 3kg | 4kg |
|---|---|---|---|---|
| Товар А | / | / | / | |
| Товар Б | / | / | 2000 | |
| Товар С | 1500 | 1500 | 2000 | |
| Товар Д | 2000 | 3500 | 3500 |
Четвертая колонка:
| Максимальный вес товарного\суб-рюкзака | 1kg | 2kg | 3kg | 4kg |
|---|---|---|---|---|
| Товар А | / | / | / | 3000 |
| Товар Б | / | / | 2000 | 3000 |
| Товар С | 1500 | 1500 | 2000 | 3500 |
| Товар Д | 2000 | 3500 | 3500 | 4000 |
Здесь достаточно делать повторные суждения, чтобы каждая ячейка была оптимальным решением, и путем решения подзадач выводится окончательное оптимальное решение. Это динамическое программирование, не правда ли просто?
Перевести вPythonКод:
def package_dp(a, b, flag, n):
c = [[0 for i in range(n)] for j in range(n)]
for j in range(n):
c[0][j] = 0
for i in range(n):
c[i][0] = 0
for j in range(n):
if b[i]>flag[j]:
c[i][j] = c[i-1][j]
else:
temp1 = a[i] + c[i-1][j-b[i]]
temp2 = c[i-1][j]
c[i][j] = max(temp1,temp2)
print c[i][j]
print ("")
return c
price = [0, 3000, 2000, 1500, 2000]
weight = [0, 4, 3, 1, 1]
flag = [0, 1, 2, 3, 4]
package_dp(price, weight, flag, 5)
3. Детали
- Задача о расщеплении подранца: по всем пунктамнаибольший общий делитель(Могут быть и десятичные знаки) для снятия субрюкзака.
Так что все товары можно просто загрузить.
- Через оптимальное решение подранца => Выводим => оптимальное решение всего ранца.
Идеей этого процесса является идея DP (основная идея динамического программирования)
В-четвертых, сценарии применения динамического программирования
В этой статье приводится пример ранцевого и матричного умножения, на самом деле идея одна и та же. Отличаются только сценарии применения.Общие сценарии применения следующие:
- 0-1 Проблема с рюкзаком ( ✔️)
- Умножение матриц ( ✔️)
- размен монет
- сходство строк
- самая длинная общая подпоследовательность
- самая длинная возрастающая подпоследовательность
- Максимальная сумма/произведение последовательной подпоследовательности
- стоимость кратчайшего пути
- Наложение плитки (состояние сжатия DP)
- Разделение рабочей нагрузки
Использованная литература:
рекомендуемая статья:
Дартс Фонд (1)
Фонд Дартс (2)
Основы дартс (3)
Основы дартс (4)
Кнопка обратного отсчета кода подтверждения SMS для iOS
Конфигурация переменной среды iOS
Общие методы обработки задач на время в iOS
Еженедельник странных танцев