Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 26, средняя оценка - 4.77
Red Planet
49 / 10 / 2
Регистрация: 20.09.2009
Сообщений: 263
#1

Задача о рюкзаке - C++

15.12.2009, 19:14. Просмотров 3592. Ответов 2
Метки нет (Все метки)

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

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

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

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

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

http://savepic.ru/978525m.jpg

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

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

Буду благодарен за помощь в решении.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
15.12.2009, 19:14     Задача о рюкзаке
Посмотрите здесь:

C++ Задача о рюкзаке
C++ Задача о рюкзаке
C++ Задача о рюкзаке
C++ Задача о рюкзаке 0-1
C++ исправьте ошибки в программе о рюкзаке
Задача о рюкзаке, решается ли она жадным алгоритмом? C++
C++ Вычислить нужную комбинацию. Задача о рюкзаке
Турист ( найти ошибку ). Вариант задачи о рюкзаке C++
C++ Разъяснение алгоритмов задачи о рюкзаке для новичков
C++ Задача о рюкзаке методом полного перебора. Нужно пояснение по коду
Задача о рюкзаке C++
C++ Задача о рюкзаке

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
#pragma
Временно недоступен
952 / 223 / 6
Регистрация: 12.04.2009
Сообщений: 921
15.12.2009, 20:17     Задача о рюкзаке #2
А при чём тут траектории? Вы пытаетесь решить задачу об оптимальных путях?
Red Planet
49 / 10 / 2
Регистрация: 20.09.2009
Сообщений: 263
15.12.2009, 20:26  [ТС]     Задача о рюкзаке #3
#pragma, насчет траектории... Понимаете, мне нужно запоиминать, сколько штук на каждом шаге я взял, чтоб в конце в ответе это написать. А траектория - это последовательность состояний.

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

Да, задача об оптимальном пути.
Yandex
Объявления
15.12.2009, 20:26     Задача о рюкзаке
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru