Задача о рюкзаке javascript

Williammer / algorithm.backpack.js

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters

function max ( a , b )

return ( a > b ) ? a : b ;

>

function knapsackRecur ( capacity , size , value , n )

if ( n == 0 || capacity == 0 )

return 0 ;

>

if ( size [ n — 1 ] > capacity )

return knapsack ( capacity , size , value , n — 1 ) ;

> else

return max ( value [ n — 1 ] +

knapsack ( capacity — size [ n — 1 ] , size , value , n — 1 ) , knapsack ( capacity , size , value , n — 1 ) ) ;

>

>

function dKnapsack ( capacity , size , value , n )

var K = [ ] ;

for ( var i = 0 ; i <= capacity + 1 ; i ++ )

K [ i ] = [ ] ;

>

for ( var i = 0 ; i <= n ; i ++ )

for ( var w = 0 ; w <= capacity ; w ++ )

if ( i == 0 || w == 0 )

K [ i ] [ w ] = 0 ;

> else if ( size [ i — 1 ] <= w )

K [ i ] [ w ] = max ( value [ i — 1 ] + K [ i — 1 ] [ w — size [ i — 1 ] ] ,

K [ i — 1 ] [ w ] ) ;

> else

K [ i ] [ w ] = K [ i — 1 ] [ w ] ;

>

putstr ( K [ i ] [ w ] + » » ) ;

>

print ( ) ;

>

return K [ n ] [ capacity ] ;

>

function ksackGreedy ( values , weights , capacity )

var load = 0 ;

vari = 0 ;

varw = 0 ;

while ( load < capacity && i < 4 )

if ( weights [ i ] <= ( capacity - load ) )

w += values [ i ] ;

load += weights [ i ] ;

> else

var r = ( capacity — load ) / weights [ i ] ;

w += r * values [ i ] ;

load += weights [ i ] ;

> ++ i ;

>

return w ;

>

var value = [ 4 , 5 , 10 , 11 , 13 ] ;

var size = [ 3 , 4 , 7 , 8 , 9 ] ;

var capacity = 16 ;

var n = 5 ;

print ( dKnapsack ( capacity , size , value , n ) ) ;

Источник

JavaScript: Задача о рюкзаке

Задача о рюкзаке — дано множество предметов с весом и стоимостью, необходимо набить рюкзак максимальной стоимостью, вес рюкзака ограничен.

solutions/solution.js

Реализуйте функцию, которая находит максимальную стоимость рюкзака, используйте динамическое программирование.

Экспортируйте функцию по умолчанию.

import solution from './solutions/solution.js'; const items = [  name: 'porridge', weight: 6, cost: 30 >,  name: 'headphones', weight: 1, cost: 20 >,  name: 'book', weight: 4, cost: 20 >,  name: 'phone', weight: 3, cost: 15 >, ]; solution(items, 9); // 55 

solutions/solution.php

Условия такие же как для JavaScript.

 $items = [ ['name' => 'porridge', 'weight' => 6, 'cost' => 30], ['name' => 'headphones', 'weight' => 1, 'cost' => 20], ['name' => 'book', 'weight' => 4, 'cost' => 20], ['name' => 'phone', 'weight' => 3, 'cost' => 15], ]; solution($items, 9); // 55 

solutions/solution.py

Условия такие же как для JavaScript.

from solution import solution ### 

solutions/Solution.java

В файле определите пакет solutions и создайте в нем публичный класс Solution . В классе создайте публичный статический метод run() , который находит максимальную стоимость рюкзака. Метод принимает два параметра:

Метод возвращает число – максимальную стоимость предметов, которые можно уместить в рюкзак

ListMapString, Object>> items = List.of( Map.of("name", "backpack", "weight", 6, "cost", 30), Map.of("name", "headphones", "weight", 1, "cost", 20), Map.of("name", "book", "weight", 4, "cost", 20), Map.of("name", "phone", "weight", 3, "cost", 15) ); Solution.run(items, 9); // 55 

Подсказки

Вспомните, как мы ходили по клеткам, и заполняли их по мере прохождения, попробуйте построить таблицу для рюкзака.

1гк	2гк	3кг	4кг	5кг	.
porridge	.
headphones	.
book	.
phone	.
.	.

Попробуйте собрать сначала рюкзак разного веса имея одну кашу (porridge) Далее, рюкзак разного веса из каши (porridge) и наушников (headphones) Затем из каши (porridge), наушников (headphones) и книги (book) . и т.д., и т.п.

Для полного доступа к испытанию нужен базовый план

Базовый план откроет полный доступ ко всем курсам, упражнениям и урокам Хекслета, проектам и пожизненный доступ к теории пройденных уроков. Подписку можно отменить в любой момент.

Источник

Задача о рюкзаке в JavaScript

Задача о рюкзаке предоставляет нам множество предметов. У каждого предмета есть вес и ценность. Нам также дается вместимость ранца — максимальный вес, который может выдержать рюкзак. Наша задача — выяснить максимальную ценность предметов, которые мы сможем уместить в рюкзаке.

Например, если у нас есть три элемента. Первый имеет значение 5 и вес 2. Второй имеет значение 2 и вес 3. Третий имеет значение 6 и вес 5. Грузоподъемность ранца равна 5. В этом случае максимальное значение будет 7, потому что мы можем нести первый и второй предметы, которые имеют более высокую общую ценность, чем если бы мы выбрали третий предмет. Первые два предмета имеют общий вес 5, поэтому мы можем взять оба. Третий предмет имеет вес 5, но его значение всего 6, поэтому лучше взять первые два предмета.

Один из способов решения этой проблемы — создать 2D-массив, в котором строки — это каждый элемент, а столбцы — это метрика веса от 0 до вместимости рюкзака. Мы начинаем со строки из всех нулей вверху, что означает отсутствие выбранных элементов. По мере того, как мы работаем по строкам, мы вычисляем максимально возможное значение для каждого веса по мере добавления каждого элемента. Например, вторая строка вычисляет максимум, добавляя только первый элемент. Третья строка вычисляет максимально возможное с первым и вторым элементами. В четвертой строке вычисляется максимально возможное с первым, вторым и третьим элементами. И так далее.

Если мы воспользуемся нашим предыдущим примером, диаграмма будет выглядеть следующим образом (первое число — это стоимость предмета, а второе — вес предмета).

Максимальный вес составляет 5, поэтому мы создаем столбец от 0 до 5. Мы делаем строку из 0, что означает, что элементы не добавляются. Затем мы добавляем первый элемент (значение: 5, вес: 2) и проходим каждое приращение веса. Если вес равен 0 или 1, мы не можем нести этот предмет, поэтому мы отмечаем эти значения как нулевые. Для любого веса 2 или больше мы можем добавить этот элемент, поэтому мы отмечаем максимальное значение как 5. Затем мы добавляем следующий элемент (значение: 2, вес: 3). Этот предмет нельзя переносить с вместимостью 0 или 1, поэтому эти столбцы помечены как 0. Когда мы дойдем до веса 2, у нас все еще есть возможность взять первый предмет, поэтому мы помечаем этот столбец как 5. Когда мы получаем вес 3, у нас есть выбор: взять первый или второй предмет. Первый элемент имеет более высокое значение, поэтому мы выбираем его и отмечаем столбец как значение первого элемента. Когда мы дойдем до веса 5, теперь мы можем нести и первый, и второй предмет с общим значением 7. Когда мы дойдем до последнего предмета (значение: 6, вес: 5), мы не сможем нести вес, элемент и имеет значение больше, чем просто взятие первых двух элементов, поэтому мы сохраняем те же максимальные значения из предыдущей строки.

Код

Чтобы закодировать это, сначала мы хотим создать наш 2D-массив, состоящий только из нулей. Количество столбцов — это емкость + 1 для нашего нулевого столбца. Количество строк — это длина элементов + 1 для расчета нашей начальной строки нулей. Мы можем сделать это, сначала создав пустой массив. Затем мы используем цикл for для создания новых массивов (строк) и используем метод fill для инициализации значений строк равными 0. Затем мы помещаем массивы строк в наш исходный пустой массив.

Затем мы собираемся использовать вложенный цикл for для перебора нашего 2D-массива и вычисления максимального общего значения для каждого приращения веса при добавлении каждого нового элемента. Мы начинаем индекс внешнего цикла с 1, потому что наша первая строка хранится со всеми 0, что означает, что элементы не должны быть добавлены. Мы также добавляем 1 к длине элементов, чтобы учесть начальную нулевую строку. Внутри внешнего цикла мы добавляем две переменные для представления текущего значения и текущего веса. Из-за этой начальной строки нулей мы устанавливаем переменные на i минус 1, поэтому она начинается с первого элемента. В этом примере у нас есть значение с индексом 0 каждого элемента и вес с индексом 1.

Внутренний цикл будет перебирать каждый столбец веса в пределах максимальной емкости. Мы начинаем индекс с 0 и добавляем 1 к максимальной емкости, чтобы учесть начальный вес 0. Мы можем добавить элемент только в том случае, если его вес меньше, чем вес текущего столбца, поэтому мы используем условие «if else» для проверки тот. Если текущий вес больше, мы берем значение из предыдущей строки в этом столбце и устанавливаем его как значение в текущей строке. Если текущий вес меньше веса столбца, мы хотим проверить, получим ли мы большее максимальное значение, добавив текущий элемент в рюкзак, или нам будет лучше с предыдущим максимальным значением этого столбца. Это можно сделать с помощью функции JavaScript math max.

Мы вычисляем ценность добавления нового элемента, беря вес текущего столбца и вычитая вес текущего элемента. Это приведет нас к столбцу в текущей строке, который показывает максимальное значение веса текущего столбца за вычетом веса текущего элемента. В нашем предыдущем примере, если мы находимся на последнем элементе (значение: 6, вес: 5) и весе столбца 5, мы вычитаем вес текущего элемента (5), что приводит нас к весу столбца 0 для этого элемента, который имеет max значение 0. Мы добавляем значение текущего элемента (6), что дает нам всего 6. Мы передаем это число и максимальное количество из предыдущей строки (7) в математическую функцию max, чтобы получить максимальное количество. Затем мы присваиваем наивысшее значение 2D-массиву.

После того, как мы перебрали все элементы, у нас теперь есть самый большой максимум в качестве последнего элемента 2D-массива. Мы можем вернуть это как MaxTotals [items.length] [capacity].

Вот окончательное решение.

Источник

Задача о рюкзаке с одним параметром

Добрый день, получил вчера следующее задание:
Есть рюкзак, который вмещает всего 50кг, также есть несколько предметов, у которых есть свой вес.
Необходимо взять любое количество предметов(без повторений), чтобы вес был наибольшим. Вот что я попробовал наработать:

Алгоритм следующий: Создаём объекты, сортируем, перебираем, выводим.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46

 html> head> title>title> head> body> script> function Item (name, massa) { this.Name = name; this.Massa = massa; } function sortItem(itemA, itemB) { return itemA.Massa - itemB.Massa; } var backpack = []; //(нет) var backpackMassa = 50; //ограничение var kol = prompt("Введите кол-во предметов"); for (var i = 0; i  kol; i++) { backpack[i] = new Item( prompt('Введите название'), prompt('Введите вес') ); } backpack.sort(sortItem); var newBackpack = 0; var backpackArray = []; for (var i = 0; i  backpack.length; i++) { if ( (+backpack[i].Massa + newBackpack)  backpackMassa ) { backpackArray.push(backpack[i]); newBackpack += +backpack[i].Massa; } } alert('Предметы которые помещаются в рюкзак:'); for (var i = 0; i  backpackArray.length; i++) { alert(backpackArray[i].Name + " " + backpackArray[i].Massa); } script> body> html>

Проблема в том, что здесь рассматривается только 1 комбинация, нежели всевозможные.
Если сделать двумерный массив, в котором будут перебираться всевозможные комбинации, а после сравниваться максимальный вес, будет ли это корректно работать для данной задачи?

Источник