Задача о ранце - это хорошо известная задача комбинаторной оптимизации. Учитывая набор элементов, каждый из которых имеет вес и значение, мы должны определить количество каждого элемента для включения в коллекцию, чтобы общий вес был меньше или равен заданному пределу, а общее значение должно быть максимальным.
Название проблемы происходит от проблемы, с которой сталкивается тот, кто ограничен рюкзаком фиксированного размера и должен вместить в него самые ценные предметы.
В этом руководстве вы собираетесь решить проблему с рюкзаком в Java в Eclipse, следуя подходу динамического программирования.
Обратите внимание, что вы также можете посмотреть это руководство в видео на YouTube:
Разработка предмета
Во-первых, мы начнем с разработки предмета для задачи о рюкзаке. Элемент будет иметь следующие свойства:
- имя помогает нам идентифицировать его
- вес, представляющий вес предмета.
- value, представляющий ценность элемента
Мы также добавляем метод str, возвращающий String представление Item. Это дает нам следующий код:
Представление решения
Как только проблема с рюкзаком будет решена, нам понадобится класс, представляющий решение. Мы сохраним максимальное значение, которое мы можем достичь, а также предметы, которые нужно включить в сумку, чтобы максимизировать ценность.
Итак, объект Solution будет иметь следующие свойства:
- значение, хранящее максимальное значение, которое мы можем достичь
- Список items ’, в котором хранятся объекты Item, которые нужно положить в сумку, чтобы получить максимальную ценность и решить проблему с рюкзаком.
Мы также добавляем метод display для вывода решения на экран. Это дает нам следующий код:
Решение проблемы с рюкзаком
Чтобы решить задачу о ранце, мы собираемся реализовать алгоритм динамического программирования. Подобно представленному в Википедии, этот алгоритм можно представить в виде псевдокода:
// Input: 2 // Values (stored in array v) 3 // Weights (stored in array w) 4 // Number of distinct items (n) 5 // Knapsack capacity (W) 6 // NOTE: The array "v" and array "w" are assumed to store all relevant values starting at index 1. 7 8 for j from 0 to W do: 9 m[0, j] := 0 10 11 for i from 1 to n do: 12 for j from 0 to W do: 13 if w[i] > j then: 14 m[i, j] := m[i-1, j] 15 else: 16 m[i, j] := max(m[i-1, j], m[i-1, j-w[i]] + v[i])
Таким образом, в матрице m значение m [i, w] будет максимальным значением, которое может быть достигнуто с весом, меньшим или равным w, с использованием элементов до i (первых i элементов).
Он дает нам следующий код Java для реализации этого алгоритма:
В конце нашего алгоритма динамического программирования максимальное значение можно найти в матрице в ячейке matrix [NB_ITEMS] [capacity].
Поиск предметов, которые нужно положить в сумку
Следующий шаг - найти предметы, которые нужно положить в сумку, чтобы получить максимальную ценность. Либо результат получается из ячейки верхней матрицы [i-1] [capacity], либо из значений [i-1] + weights [i-1] [capacity-weights [i-1]], как в матрице, построенной ранее.
Если он идет последним, это означает, что предмет включен в сумку, чтобы максимизировать ценность. Он дает нам следующий код, чтобы найти элементы, которые нужно включить:
Сборка всех деталей
В конце метода resolve мы возвращаем объект Solution, содержащий максимальное значение value и список items ' включить в сумку. Мы также добавляем метод display в объект Knapsack для вывода на экран исходной задачи о рюкзаке.
Наконец, мы добавляем основную точку входа и собираем все части для создания задачи о ранце, отображаем ее на экране, решаем и затем отображаем решение.
Это дает нам следующий код для класса Knapsack:
Наш решатель в действии
Последний шаг - запустить наш инструмент для решения проблем с рюкзаком. Рассмотрим следующий пример задачи о ранце:
- Сумка вместимостью 15кг.
- 5 предметов на выбор с определенными значениями и весом
Мы запускаем наш решатель задач с рюкзаком с этим экземпляром. По окончании выполнения решение отображается в консоли:
Таким образом, значение увеличивается до 15 за счет включения элементов 2, 3, 4 и 5 в сумку.
Вот и все для этого урока!
Чтобы найти больше руководств по разработке на Java, вы можете подписаться на канал SSaurel:
Если вы хотите открыть для себя несколько книг по программированию на Java, я советую вам прочитать следующую статью с моей подборкой из 6 лучших книг по программированию на Java:
