Предположим, у вас есть 10 задач, которые вам нужно выполнить за определенное время, но, учитывая время, количество задач и время на выполнение каждой задачи, вы не можете выполнить их все за заданное время. Итак, на каких задачах следует сосредоточиться?
Что, если каждая задача имеет определенное значение. Например, если вы выполните эту задачу, вы можете увеличить продажи на x сумму. Наряду со значением вы также можете выделить вес, который в этом случае будет ограничением по времени. Таким образом, у вас есть список задач с установленным временем выполнения, и каждая задача добавляет свою ценность выполнению.
Это пример задачи комбинаторной оптимизации, известной как задача о рюкзаке. Существует другая версия задачи о рюкзаке, но в данном случае основное внимание уделяется задаче о рюкзаке 0–1. В задаче о рюкзаке 0–1 предмет (или задача) либо полностью включен, либо не включен вовсе. В других задачах с рюкзаком вы можете частично включать элементы или иметь несколько целей или даже задачу с несколькими рюкзаками, где у вас есть несколько ресурсов, которые могут выполнять задачи.
Далее в этом проекте внимание будет сосредоточено только на упрощенной версии одной цели и одного рюкзака. Задача о рюкзаке 0–1 может быть математически смоделирована следующим образом:
xᵢуказывает, следует ли элементi включать в решение или нет. wᵢ — это вес элемента i, а vᵢ — значение элемента i. W — это общий вес, который не может превышать все элементы, включенные в решение.
Конечная цель — создать веб-приложение, в котором вы можете вводить элементы с весами и значениями. Но для этого необходимо сначала рассмотреть способ решения задачи о рюкзаке 0–1. В данном случае основное внимание уделяется методу динамического программирования для решения задачи о рюкзаке.
Далее следует псевдокод для метода динамического программирования. У нас есть таблица B[n, W] и мы заполняем ее следующим образом:
1: Set B[0,w] = 0 for w=0 to W
2: Set B[i,0] = 0 for i=0 to n
3: If wᵢ ≤ w Then B[i,w]=max(vᵢ+B[i-1,w-w_i ],B[i-1,w])
Else B[i,w]= B[i-1,w]
Как только таблица заполнена, мы возвращаемся к B[n, W], которая дает максимальное значение, чтобы определить, какие элементы следует включить.
1: If B[i,j] > B[i-1,j] Then include Item i in selection 2: Evaluate B[j-1,j- wᵢ]. If B[j-1,j- wᵢ] > 0 then repeat step 2 3: Return selected items
Эта логика, решающая проблему рюкзака 0-1, была встроена в веб-приложение с использованием HTML, CSS и Vanilla Javascript. Приложение можно найти в разделе,
Затем следует ввести максимальный вес, а затем предметы внизу. Чтобы добавить новые предметы, нажмите кнопку «Добавить элемент» и заполните описание предмета, а также его стоимость и вес.
Вы также можете загрузить элементы из CSV-файла с описанием, стоимостью, весом (за исключением заголовков) с помощью кнопки «Загрузить». Если вы хотите удалить элемент, нажмите кнопку «Корзина» рядом с каждым элементом, который удалит элемент.
После того, как элементы заполнены, нажмите кнопку «Рассчитать», которая предоставит результат максимального значения, а также будет обновлен индикатор включения, указывающий, какие элементы должны быть включены.
Вот пример конечного результата
Преобразование задачи о рюкзаке 0–1 с динамическим программированием в язык программирования довольно просто и должно быть для любого другого языка, кроме Javascript. Любая проблема 0–1 должна быть решена с помощью приложения, а наличие веб-приложения означает, что вам просто нужно ввести свою информацию.
Для дальнейшей разработки результаты этого приложения можно экспортировать из приложения и, возможно, связать с другими приложениями, которым требуется информация или логика, встроенная непосредственно в другие приложения.
