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

Основы алгоритмов и структур данных
Обновлено: 30 нояб., 13:46
190
Студентов
65%
Завершения

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

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.

<?php

$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(), который находит максимальную стоимость рюкзака. Метод принимает два параметра:

  • Список предметов List<Map<String, Object>>
  • Максимальный вместимость рюкзака, число int

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

List<Map<String, 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) ... и т.д., и т.п.

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

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

Получить доступ
1000
упражнений
2000+
часов теории
3200
тестов