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

@Yologamer · Регистрация: 25.09.2016

Author24 — интернет-сервис помощи студентам

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

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

PHP/HTML

<!DOCTYPE html> 
<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 комбинация, нежели всевозможные.
Если сделать двумерный массив, в котором будут перебираться всевозможные комбинации, а после сравниваться максимальный вес, будет ли это корректно работать для данной задачи?

@Yologamer · 13.03.2019, 23:33 **[ТС]**

Доброго вечера всем. Поставили задачу, в которой необходимо найти наиболее приближенный порядок элементов массива к задданому числу. Я нашел примеры кода, где вес и стоимость различаются.
Буду рад, если кто поделится ссылкой или информацией с кодом, для решения такого рода задачи.

Комментарий модератора

Правила форума

4. Порядок создания тем.
4.13 Если на ваш вопрос долгое время нет ответа, уточните его, приведите дополнительные сведения, которые могут помочь участникам форума решить вашу проблему.
4.14 Чтобы "поднять" тему в разделе и поиске по форуму, используйте осмысленные сообщения, например "Тема/проблема/задача актуальна". Если вы чего-то достигли в решении проблемы на этот момент, сообщите об этом.

5. Запреты и ограничения.
5.5 Запрещено размещать тему в нескольких подразделах одного раздела одновременно (кросспостинг), а также дублировать тему в одном разделе.

	13.03.2019, 23:33