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

@Red Planet · Регистрация: 20.09.2009

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

Доброго вечера! Даны n типов предметов, каждый тип обладает своей стоимостью и весом, а также предел грузоподъемности limit. Нужно набрать максимум стоимости и не превысить грузоподъемность. За состояние на каждом шаге принимаем уже израсходованный ресурс.

На n-ом можем взять столько предметов n-ого типа, сколько захотим, лишь бы только не превысить грузоподъемность. На первом это количество равно (limit/mas1)+1, где mas1 - масса 1-ого предмета, единицу прибавляем, так как можем и не брать данный предмет.

Идеи пока что следующие.
1. Делаем class thing, объектом такого класса будет являться наш предмет, имеющий две характеристики: массу и стоимость.
2. Делаем динамический двумерный массив типа thing, где количество столбцов - количество типов предметов, а строки на каждом шаге определяются динамически.

Пример
Три типа предметов, указаны: масса (стоимость). 20 (15), 30 (20), 35 (40). Грузоподъемность 60.

Начинаем работать в прямом направлении слкедующим образом:

На каждом шаге отсеиваем неоптимальные траектории. Допустим, на i-ом шаге имеются два пути, сходищихся в одной точке - 20 (30) и 20 (35), в этом случае все продолжения 20 (30) не рассматриваем, т. к. 30<35.

Насчет программной реализации. Предлагается хранить не сами состояния, а траектории (насколько я придумал, создается двумерный массив типа thing (класс определен выше), 8 столбцов, а вот число строк определяется динамически, т. е. на каждом шаге оно разное, в зависимости от количества состояний, сразу вопрос: как это сделать?), На последнем (в примере на третьем шаге просто ищем состояние я максимальной стоимостью, оно и будет являться ответом)

Буду благодарен за помощь в решении.

@#pragma · 15.12.2009, 20:17

А при чём тут траектории? Вы пытаетесь решить задачу об оптимальных путях?

@Red Planet · 15.12.2009, 20:26 **[ТС]**

#pragma, насчет траектории... Понимаете, мне нужно запоиминать, сколько штук на каждом шаге я взял, чтоб в конце в ответе это написать. А траектория - это последовательность состояний.

20 (15) - некоторое состояние на первом шаге.
Допустим на втором взяли три предмета второго типа (30*3=90, 20*3=60, т.е. 90 (60)), тогда траектория будет выглядеть следующим образом:
20 (15) - 110 (75) - вот так.

Да, задача об оптимальном пути.

Новые блоги и статьи Все статьи Все блоги /
моя боль iceja 24.01.2026 Выложила интерполяцию кубическими сплайнами www. iceja. net REST сервисы временно не работают, только через Web. Написала за 56 рабочих часов этот сайт с нуля. При помощи perplexity. ai PRO , при. . .	Модель сукцессии микоризы anaschu 24.01.2026 Решили писать научную статью с неким РОманом	http://iceja.net/ математические сервисы iceja 20.01.2026 Обновила свой сайт http:/ / iceja. net/ , приделала Fast Fourier Transform экстраполяцию сигналов. Однако предсказывает далеко не каждый сигнал (см ограничения http:/ / iceja. net/ fourier/ docs ). Также. . .	http://iceja.net/ сервер решения полиномов iceja 18.01.2026 Выкатила http:/ / iceja. net/ сервер решения полиномов (находит действительные корни полиномов методом Штурма). На сайте документация по API, но скажу прямо VPS слабенький и 200 000 полиномов. . .
Расчёт переходных процессов в цепи постоянного тока igorrr37 16.01.2026 / * Дана цепь(не выше 3-го порядка) постоянного тока с элементами R, L, C, k(ключ), U, E, J. Программа находит переходные токи и напряжения на элементах схемы классическим методом(1 и 2 з-ны. . .	Восстановить юзерскрипты Greasemonkey из бэкапа браузера damix 15.01.2026 Если восстановить из бэкапа профиль Firefox после переустановки винды, то список юзерскриптов в Greasemonkey будет пустым. Но восстановить их можно так. Для этого понадобится консольная утилита. . .	Сукцессия микоризы: основная теория в виде двух уравнений. anaschu 11.01.2026 https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/	WordPad для Windows 11 Jel 10.01.2026 WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .

@Red Planet 49 / 10 / 3 Регистрация: 20.09.2009 Сообщений: 263

	Задача о рюкзаке 15.12.2009, 19:14. Показов 8543. Ответов 2 Метки нет (Все метки) Доброго вечера! Даны n типов предметов, каждый тип обладает своей стоимостью и весом, а также предел грузоподъемности limit. Нужно набрать максимум стоимости и не превысить грузоподъемность. За состояние на каждом шаге принимаем уже израсходованный ресурс. На n-ом можем взять столько предметов n-ого типа, сколько захотим, лишь бы только не превысить грузоподъемность. На первом это количество равно (limit/mas1)+1, где mas1 - масса 1-ого предмета, единицу прибавляем, так как можем и не брать данный предмет. Идеи пока что следующие. 1. Делаем class thing, объектом такого класса будет являться наш предмет, имеющий две характеристики: массу и стоимость. 2. Делаем динамический двумерный массив типа thing, где количество столбцов - количество типов предметов, а строки на каждом шаге определяются динамически. Пример Три типа предметов, указаны: масса (стоимость). 20 (15), 30 (20), 35 (40). Грузоподъемность 60. Начинаем работать в прямом направлении слкедующим образом: На каждом шаге отсеиваем неоптимальные траектории. Допустим, на i-ом шаге имеются два пути, сходищихся в одной точке - 20 (30) и 20 (35), в этом случае все продолжения 20 (30) не рассматриваем, т. к. 30<35. Насчет программной реализации. Предлагается хранить не сами состояния, а траектории (насколько я придумал, создается двумерный массив типа thing (класс определен выше), 8 столбцов, а вот число строк определяется динамически, т. е. на каждом шаге оно разное, в зависимости от количества состояний, сразу вопрос: как это сделать?), На последнем (в примере на третьем шаге просто ищем состояние я максимальной стоимостью, оно и будет являться ответом) Буду благодарен за помощь в решении. 0

@#pragma Временно недоступен 957 / 228 / 14 Регистрация: 12.04.2009 Сообщений: 926
	15.12.2009, 20:17
	А при чём тут траектории? Вы пытаетесь решить задачу об оптимальных путях? 0

@Red Planet 49 / 10 / 3 Регистрация: 20.09.2009 Сообщений: 263
	15.12.2009, 20:26 [ТС]
	#pragma, насчет траектории... Понимаете, мне нужно запоиминать, сколько штук на каждом шаге я взял, чтоб в конце в ответе это написать. А траектория - это последовательность состояний. 20 (15) - некоторое состояние на первом шаге. Допустим на втором взяли три предмета второго типа (303=90, 203=60, т.е. 90 (60)), тогда траектория будет выглядеть следующим образом: 20 (15) - 110 (75) - вот так. Да, задача об оптимальном пути. 1