Rivalry2

HTML Diff

0 added 0 removed

Original 2026-01-01

Modified 2026-02-21

1 <a>#статьи</a>

2 <ul><li>20 апр 2021</li>

3 <li>0</li>

4 </ul><h2>Динамическое программирование - это просто. Решаем задачу о рюкзаке</h2>

5 Объясняем на пальцах, как использовать приёмы динамического программирования в жизни и на работе.

6 Фулстек-разработчик. Любимый стек: Java + Angular, но в хорошей компании готова писать хоть на языке Ада.

7 Вам никогда не хотелось бросить всё и уйти из дома с одним рюкзаком? Мне да, но институт, экзамены, сессия родственники, ипотека, кот - так что не вариант.

8 Но если бы я собирала такой рюкзак, то положила бы в него вещи, которые можно продать побыстрее и подороже, - чтобы выручить денег для новой жизни в новом месте.

9 У нас есть довольно вместительный рюкзак и дорогие вещи, которые можно в него положить. Но вот беда - лямки рюкзака выдерживают, скажем, четыре килограмма, не больше.

10 А выбираем мы:

11 <ul><li>из ноутбука, который весит три килограмма и стоит 2 000 долларов;</li>

12 <li>бензопилы(ею ещё можно отмахиваться от назойливых попутчиков) - четыре килограмма мощи, которые обойдутся новому владельцу в 3 000 долларов;</li>

13 <li>и мини-гитары - весит килограмм, а продать её можно за 1 500 долларов.</li>

14 </ul>Нам нужно выбрать вещи наибольшей общей стоимости и не забывать про хилые лямки рюкзака.

15 Это полный перебор, конечно! Из трёх предметов можно составить всего восемь комбинаций. Подсчитаем стоимость для каждой и выберем самый выгодный вариант:

16 Пока предметов только три - вполне себе годное решение, но добавим ещё один - и вариантов станет 16, а для пяти их будет уже 32.

17 С добавлением каждого нового предмета число комбинаций удваивается, так что сложность такого алгоритма - O(2n). Это медленный способ.

18 Применим так называемыйжадный алгоритм: на каждом шаге добавляем в рюкзак самый дорогой предмет, пока лимит веса не превышен.

19 В случае с нашими предметами - одним шагом дело бы и закончилось. Мы сразу же взяли бы бензопилу за 3 000 долларов, потому что она самая дорогая. А при добавлении любого нового предмета в рюкзаке уже был бы перевес.

20 Было ли наше решение оптимальным? Нет, потому что гитару на пару с ноутбуком наш рюкзак тоже выдержит, но стоят они 1 500 долларов + 2 000 долларов = 3 500 долларов, что больше 3 000 долларов.

21 Воспользуемся приёмамидинамического программирования. Разобьём задачу на подзадачи и будем последовательно их решать. При этом на каждом следующем шаге используем результаты предыдущего.

22 Наглядно это можно представить в виде таблицы. Её ещё называют таблицей мемоизации. Столбцы нашей соответствуют килограммам (от одного до четырёх), а строки - предметам (гитара, бензопила, ноутбук).

23 1 кг 2 кг 3 кг 4 кг гитара бензопила ноутбукТаблица до заполнения

24 На пересечении, в ячейках, будем записывать общую стоимость предметов в рюкзаке.

25 Гитара

26 Для каждого столбца (та или иная грузоподъёмность рюкзака) нужно решить: класть гитару в рюкзак или нет.

27 Так как гитара весит всего один килограмм, то она влезет уже на первом шаге. Поэтому в каждой ячейке первой строки напишем 1 500 - стоимость гитары.

28 Мы заполнили строку целиком и узнали, чтопромежуточный максимум для рюкзака в четыре килограмма составляет 1500 долларов.

29 1 кг 2 кг 3 кг 4 кг гитара 1 500 1 500 1 5001 500бензопила ноутбукТаблица для первого предмета - гитары

30 Бензопила

31 На следующем этапе рассматриваем двух кандидатов - гитару и бензопилу.

32 В рюкзаки, рассчитанные на один, два или три килограмма, бензопилу не положить, так что оставляем там гитару и максимум стоимости вещей 1 500 долларов. А вот для случая "четыре килограмма" обновляем максимум: кладём бензопилу стоимостью 3 000 долларов.

33 1 кг 2 кг 3 кг 4 кг гитара 1 500 1 500 1 500 1 500 бензопила 1 500 1 500 1 5003 000ноутбукТаблица для двух предметов - гитары и бензопилы

34 Ноутбук

35 Добавим последний предмет - ноутбук.

36 Для первых двух столбцов ничего не меняется, так как ничего, кроме гитары, в рюкзаки с грузоподъёмностью один и два килограмма положить не получится.

37 Зато в трёхкилограммовый рюкзак уже можно вместо гитары положить ноутбук - он дороже, обновляем максимум в этом столбце до 2 000 долларов.

38 Интереснее всего ситуация в последней ячейке: мы можемположить ноутбук, но он весит всего три килограмма, ещё один килограмм остаётся свободным.

39 И вот тут, наконец, пригодятся промежуточные результаты: мы узнали на предыдущих шагах максимальную стоимость для рюкзака, который выдерживает один килограмм, - она равна 1 500 долларов.

40 В итоге получаем ноутбук + гитара = 3 500 долларов, это больше предыдущего максимума в 3 000 долларов. Так что ответ в задаче -3 500 долларов.

41 1 кг 2 кг 3 кг 4 кг гитара 1 500 1 500 1 500 1 500 бензопила 1 500 1 500 1 500 3 000 ноутбук 1 500 1 500 2 0003500Таблица для всех трёх предметов

42 В общем случае формула для стоимости в каждой ячейке выглядит так:

43 S[i, j] = max (S[i-1, j], цена i-го предмета + S[i-1, j-вес i-го предмета]),

44 где i - номер строки, j - столбца.

45 То есть на каждом шаге мы выбираем между предыдущим максимумом и суммой, которую составляют стоимость текущего предмета и максимальная цена незанятого веса.

46 Определим класс для вещей, которые можно положить в рюкзак:

47 public static class Item { private final String name; //название вещи private final int weight; //вес private final int price; //стоимость public Item(String name, int weight, int price) { this.name = name; this.weight = weight; this.price = price; } public String getName() { return name; } public int getWeight() { return weight; } public int getPrice() { return price; } }И класс для промежуточного состояния - содержимого ячейки таблицы. Будем хранить, какие вещи на этом этапе лежат в рюкзаке, а также их общую стоимость.

48 public Backpack(Item[] items, int price) { this.items = items; this.price = price; } public Item[] getItems() { return items; } public int getPrice() { return price; } //Описание состояния рюкзака public String getDescription() { return items == null ? "" : Arrays.stream(items).map(Item::getName).collect(Collectors.joining("+")) + "-" + getPrice(); } }Чтобы сократить запись и уменьшить количество циклов, здесь и далее приводим вставки кода с использованием Java Stream API. Если вы мало знакомы с такой записью, почитайте о стримах<a>здесь</a>.

49 Определимся с исходными данными:

50 int n = 3; //число строк = число вещей int k = 4; //грузоподъёмность рюкзака //массив вещей Item[] items = {new Item("гитара", 1, 1500), new Item("бензопила", 4, 3000), new Item("ноутбук", 3, 2000)}; //массив промежуточных состояний рюкзака Backpack[][] bp = new Backpack[n + 1][k + 1];А теперь реализуем на Java описанный выше алгоритм заполнения таблицы:

51 for (int i = 0; i < n + 1; i++) { for (int j = 0; j < k + 1; j++) { if (i == 0 || j == 0) { //нулевую строку и столбец заполняем нулями bp[i][j] = new Backpack(new Item[]{}, 0); } else if (i == 1) { /*первая строка заполняется просто: первый предмет кладём или не кладём в зависимости от веса*/ bp[1][j] = items[0].getWeight() <= j ? new Backpack(new Item[]{items[0]}, items[0].getPrice()) : new Backpack(new Item[]{}, 0); } else { if (items[i - 1].getWeight() > j) //если очередной предмет не влезает в рюкзак, bp[i][j] = bp[i - 1][j]; //записываем предыдущий максимум else { /*рассчитаем цену очередного предмета + максимальную цену для (максимально возможный для рюкзака вес - вес предмета)*/ int newPrice = items[i - 1].getPrice() + bp[i - 1][j - items[i - 1].getWeight()].getPrice(); if (bp[i - 1][j].getPrice() > newPrice) //если предыдущий максимум больше bp[i][j] = bp[i - 1][j]; //запишем его else { /*иначе фиксируем новый максимум: текущий предмет + стоимость свободного пространства*/ bp[i][j] = new Backpack(Stream.concat(Arrays.stream(new Item[]{items[i - 1]}), Arrays.stream(bp[i - 1][j - items[i - 1].getWeight()].getItems())).toArray(Item[]::new), newPrice); } } } } }Напишем небольшой фрагмент кода для вывода полученной в итоге таблицы:

52 for (int i = 1; i < n + 1; i++) { for (int j = 1; j < k + 1; j++) { System.out.print(bp[i][j].getDescription() + " "); } System.out.print("\n"); }И убедимся, что результат запуска этого фрагмента совпадает с таблицей, которую мы получили вручную:

53 Дело за малым - найти в этой таблице ответ на задачу: какие предметы нужно взять и сколько за них в лучшем случае можно выручить. Ответ находится в последнем столбце таблицы: именно в нём записана стоимость предметов для четырёх килограммов - максимально допустимого веса нашего рюкзака.

54 Так что нужно перебрать все записи в этом столбце и найти сочетание с наибольшей стоимостью. Это можно сделать так:

55 List<Backpack> lastColumn = Arrays.stream(backpack).map(row -> row[row.length - 1]).collect(Collectors.toList()); Backpack backpackWithMax = lastColumn.stream().max(Comparator.comparing(Backpack::getPrice)).orElse(new Backpack(null, 0)); System.out.println(backpackWithMax.getDescription());Чтобы отдохнуть от рутины, необязательно уходить из дома насовсем, достаточно выбраться в новое интересное место на пару-тройку дней.

56 Скажем, вы приезжаете в Санкт-Петербург на выходные и хотите увидеть как можно больше достопримечательностей. Каждую вы оценили в баллах - насколько сильно вам это место интересно. Кроме того, прикинули время, которое уйдёт на осмотр.

57 Посмотрим, что там у вас:

58 <ul><li>Эрмитаж - восемь баллов и половина дня;</li>

59 <li>фонтаны в Петергофе - десять баллов и день;</li>

60 <li>сфинксы на набережной - семь баллов и четверть дня;</li>

61 <li>Исаакиевский собор с колокольней - шесть баллов и полдня;</li>

62 <li>и так далее на ваш вкус.</li>

63 </ul>По сути это ровно та же задача о рюкзаке. Только грузоподъёмность - это дни (у вас их два), стоимость - оценка в баллах, вес - время, которое уходит на осмотр. Нужно найти комбинацию достопримечательностей с наивысшей оценкой.

64 Для решения подойдёт таблица с шагом в четверть дня. В ней будет восемь столбцов, а строк столько, сколько достопримечательностей вы хотите увидеть.

65 Так вы без труда составите оптимальный план.

66 Приходите на курс "<a>Алгоритмы и структуры данных для разработчиков</a>". Это та необходимая база, которая структурирует мышление - и меняет подход, делает программиста из обычного кодера. Студенты решают самые разные задачи, на практике осваивают важнейшие структуры данных и золотой арсенал алгоритмов, оценивают ресурсную эффективность решений и учатся оптимизировать чужой код.

67 <a>Научитесь: Алгоритмы и структуры данных для разработчиков Узнать больше</a>