Если вас интересуют другие задачи динамического программирования, вы также можете просмотреть
В начале, когда я соприкоснулся с динамическим программированием, я мог растеряться, как будто мог понять идею, но не мог точно выразить или написать код. Эта статья поможет учащимся, плохо знакомым с динамическим программированием, шаг за шагом разобраться в проблеме посредством рисования. Этот будет основан на классике01 РюкзакПроблема объясняется в качестве примера и, наконец, реализована на чистом JavaScript, запустив демонстрацию в Sublime. Конечно, не беда, если вы не знаете JavaScript, ведь самое главное — понять весь процесс вывода. Когда язык реализован, он не предполагает каких-либо особенностей языка, в принципе, вы можете понять его, если знаете язык Си.
вопрос
Дан рюкзак фиксированных размеров, вместимостью рюкзака является вместимость, имеется набор предметов, соответствующие величины и веса, требуется найти оптимальное решение такое, чтобы общий вес предметов, загруженных в рюкзак, составлял не превышать вместимость рюкзака, а общая стоимость является наибольшей. В этой задаче есть 3 элемента, стоимость и вес которых равны (3,2),(4,3),(5,4). В левой части скобок указано значение, в правой — вес, а вместимость рюкзака — 5. Затем найдите комбинацию, при которой общая стоимость рюкзака будет наибольшей, и каково максимальное значение?
анализировать
Прежде чем приступить к расчету, необходимо иметь базовое представление о задаче 01 о рюкзаке в динамическом программировании:
- Элементы не могут быть разделены на дроби. Если они могут быть разделены, это проблема жадного алгоритма. Мы также представим жадный алгоритм в следующей статье.
- Не обязательно именно полный рюкзак.
- Общая стоимость не обязательно является наибольшей при заполнении.
- Один из каждого элемента
- При нормальных обстоятельствах в таблице цены и веса обычно увеличиваются сверху вниз. Когда мы заполняли форму для анализа, мы на самом деле неявно предполагали эту возрастающую связь заранее.
После того как изложенные выше принципы станут ясны, можно приступать к анализу.
Когда появляется новый предмет, необходимо решить, максимизирует ли его выбор общую стоимость. По задаче мы составили следующую таблицу для анализа:
Поясним эту форму, верхний левый уголvalа такжеw- стоимость и вес предмета соответственно. То есть стоимость и вес трех описанных выше предметов соответствуют друг другу.
От третьего до последнего столбца используется переменная j, которая представляет общую вместимость рюкзака, и максимальное значение равно 5, что является значением вместимости, упомянутым в предыдущем вопросе.
Вторая строка до последней строки представлена i, нижний индекс начинается с 0, и всего 3 элемента, поэтому максимальное значение i равно 2. То есть мы используем i для представления элемента, который будет описан в следующем введении.i=0называется物品0,i=1называется物品1, и так далее.
За исключением случая j = 0, мы будем заполнять эту форму шаг за шагом слева направо, сверху вниз, чтобы найти наибольшее значение.
Незаполненные поля в форме указывают на общую стоимость предметов в рюкзаке. мы будем использовать позжеT[i][j]2D-массив для его представления.
1. Когда общая емкость равна 0
Если общая вместимость рюкзака равна 0, то, очевидно, в рюкзак ничего не может поместиться, поэтому общая стоимость в рюкзаке должна быть равна 0. Итак, первый шаг — заполнить случай j=0.
2. Линия 0, пространственный анализ для i = 0
Как упоминалось выше, мы будем заполнять эту форму сверху вниз, слева направо. Итак, теперь сосредоточьтесь на пространстве, где i = 0, j = 1.
В процессе анализа существует важный принцип:分析第i行时，它的物品组合仅能是小于等于i的情况。
Как понять этот принцип: например, анализi=0Эта линия, то в рюкзак может поместиться толькопункт 0, другие элементы не могут быть загружены. анализироватьi=1В этом ряду комбинация предметов может бытьпункт 0а такжепункт 1
i=0 j=1 : Общая вместимость рюкзака равна 1, но вес предмета 0 равен 2, который нельзя загрузить, поэтому этот слот должен быть заполнен.0.
i=0 j=2 : общая вместимость рюкзака равна 2, этого достаточно, чтобы вместить предмет 0. Поскольку значение предмета 0 равно 3, этот ящик заполнен3.
i=0 j=3 : Общая вместимость рюкзака равна 3. Согласно описанному выше принципу комбинирования предметов, в строке 0 можно разместить только предмет 0, а предмет 1 и предмет 2 учитывать не нужно, поэтому заполните это поле.3.
i=0 j=4 : Аналогично заполнить3.
i=0 j=5 : Аналогично заполнить3.
Таким образом, мы можем завершить заполнение строки 0, как показано ниже:
3. Строка 1, пространственный анализ для i = 1
В этом ряду предметы 0 и 1 можно свободно комбинировать, чтобы они поместились в рюкзак.i=1 j=1 : Общая вместимость рюкзака равна 1, но вес предмета 0 равен 2, а вес предмета 1 равен 3. Рюкзак не может вместить никакие предметы, поэтому заполните0.
i=1 j=2 : общая вместимость рюкзака равна 2, и он может вместить только 0 предметов, поэтому заполните3.
i=1 j=3 : Общая вместимость рюкзака 3. В это время может быть загружен предмет 1 или предмет 0. Несложно понять, что предмет 1 нужно выбрать из ручного заполнения формы, но как выразить это с точной логикой, так что понимает ли компьютер? Основываясь на принципе увеличения значения и веса сверху вниз в таблице, можно подтвердить, что значение элемента 1 больше, чем значение элемента 0, поэтому по умолчанию приоритет отдается элементу 1. Когда элемент 1 выбрали, остальные предметы положите в рюкзак Вместимость сравнивается с весом предмета до предмета 1 (то есть сравнивается с весом предмета 0, если оставшийся вес может поместиться в предыдущий предмет, то продолжайте загрузку). Итак, выберите здесь пункт 1, заполните4
i=1 j=4 : После выбора элемента 1 вес предмета 1 равен 3, а вместимость рюкзака равна 4. После вычитания веса предмета 1 оставшаяся вместимость равна 1, а предмет 0 не может быть загружен, поэтому заполните здесь4
i=1 j=5 После выбора предмета 1 оставшаяся емкость равна 2, чего достаточно для хранения предмета 0, поэтому предмет 1 и предмет 0 упакованы в одну упаковку, а общая стоимость равна 7.7Заполнить форму.
Это завершает заполнение второй строки, как показано ниже:
3. Строка 2, пространственный анализ для i = 2
i=2 j=1 : Заполнить0.
i=2 j=2 : При заполнении этой строки все 3 предмета имеют шанс загрузиться в рюкзак. Когда общая вместимость равна 2, можно загрузить только 0 предметов, поэтому заполните3.
i=2 j=3 : Вес предмета 2 равен 4, что больше, чем вместимость j, поэтому здесь вы можете обратиться к значению T[i-1][j], которое равноi=1 j=3Значение этого поля, заполните4.
i=2 j=4 : Может содержать элемент 2 со значением 5. Может также содержать пункт 1. Это пространство требует осторожности. Мы будем использовать более строгий подход к нашему анализу. существуетi=1 j=5 Есть случай, когда комбинация предметов кладется в рюкзак вместе, и этот зазор продолжит этот метод анализа. Мы выбрали пункт 2, выражение оставшейся емкости должно бытьj-w[i]который4 - 4 = 0, оставшаяся емкость используется для поиска предыдущей строки.Поскольку мы заполнили предыдущую строку, это значение может быть легко получено. Выражение можно записать какval[i] + T[i-1][j-w[i]], значение может быть получено из этого выражения. Но это не окончательный результат, его еще нужно сравнить со значением того же столбца в предыдущей строке, т.е.T[i-1][j], напротив, берем максимальное значение. Наконец заполните здесь5.
i=2 j=5 : В соответствии с приведенным выше принципом расчета, если здесь выбран пункт 2, максимальное значение может быть только 5. Обратитесь к предыдущей строке и тому же столбцу, значение равно 7, и берется максимальное значение. Так что откажитесь от предмета 2, положите предмет 0 и предмет 1 в рюкзак и заполните 7.
Заполненная форма выглядит следующим образом:
Выражение псевдокода
После понимания всего вышеописанного процесса заполнения формы нам нужно извлечь логику и выразить ее в псевдокоде, прежде чем конкретный код будет реализован.
if(j < w[i]){ //容量小于重量，hold不住
T[i][j] = T[i-1][j]; //所以值等于上一行，同一列。如果i=0,没有上一行，则T[i][j] 取0
}else{
T[i][j] = max(val[i] + T[i-1][j-w[i]] , T[i-1][j]); //参照上面 i=2 j=4 和 i=2 j=5 时的填表分析
}
Приведенный выше короткий псевдокод является основной идеей задачи, и его можно применить к любому знакомому вам языку программирования.
Сказав это, эта статья должна в основном подойти к концу.
Реализация JavaScript
Если вы поняли приведенный выше анализ заполнения формы и выражение псевдокода, то можете попробовать реализовать его самостоятельно. Наконец, для вашего ознакомления выпущен метод реализации с использованием JavaScript, пояснений к коду больше не будет, а в важных местах будут комментарии. Если Sublime поддерживает чистый JavaScript, вы можете скопировать и вставить его напрямую и запустить команду + b, чтобы увидеть результат.
function knapSack(w,val,capacity,n){
var T = []
for(let i = 0;i < n;i++){
T[i] = [];
for(let j=0;j <= capacity;j++){
if(j === 0){ //容量为0
T[i][j] = 0;
continue;
}
if(j < w[i]){ //容量小于物品重量，本行hold不住
if(i === 0){
T[i][j] = 0; // i = 0时，不存在i-1，所以T[i][j]取0
}else{
T[i][j] = T[i-1][j]; //容量小于物品重量，参照上一行
}
continue;
}
if(i === 0){
T[i][j] = val[i]; //第0行，不存在 i-1, 最多只能放这一行的那一个物品
}else{
T[i][j] = Math.max(val[i] + T[i-1][j-w[i]],T[i-1][j]);
}
}
}
findValue(w,val,capacity,n,T);
return T;
}
//找到需要的物品
function findValue(w,val,capacity,n,T){
var i = n-1, j = capacity;
while ( i > 0 && j > 0 ){
if(T[i][j] != T[i-1][j]){
console.log('选择物品'+i+',重量：'+ w[i] +',价值：' + values[i]);
j = j- w[i];
i--;
}else{
i--; //如果相等，那么就到 i-1 行
}
}
if(i == 0 ){
if(T[i][j] != 0){ //那么第一行的物品也可以取
console.log('选择物品'+i+',重量：'+ w[i] +',价值：' + values[i]);
}
}
}
// w = [2,3,4]. val = [3,4,5] , n = 3 , capacity = 5
//function knapSack([2,3,4],[3,4,5],5,3);
//
var values = [3,4,5],
weights = [2,3,4],
capacity = 5,
n = values.length;
console.log(knapSack(weights,values,capacity,n));
выходной результат