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

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

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

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

15.12.2009, 19:14. Просмотров 3743. Ответов 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 столбцов, а вот число строк определяется динамически, т. е. на каждом шаге оно разное, в зависимости от количества состояний, сразу вопрос: как это сделать?), На последнем (в примере на третьем шаге просто ищем состояние я максимальной стоимостью, оно и будет являться ответом)

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

Задача о Рюкзаке - C++
Очень прошу с помощью. Нужен код на с++, решение задачи о рюкзаке методами : динамического программирования, метод ветвей и границ , жадный...

Задача о рюкзаке - C++
И так я все сделал как вы и просили. Условие задачи о рюкзаке: Итак, пусть у нас есть рюкзак объёма W, и список из n вещей, у каждой...

Задача о рюкзаке - C++
Привет ребята, требуется помощь. Если есть у кого - то выложите пожалуйста код реализации алгоритма задачи о рюкзаке &quot;Задача о рюкзаке...

Задача о рюкзаке - C++
Мне нужно сдать программу на си на задачу о рюкзаке: из n предметов, для которых заданы вес и стоимость, выбрать такие, чтобы суммарный вес...

Задача о рюкзаке - C++
Здравствуйте, нужно реализовать задачу о рюкзаке (из заданного множества предметов со свойствами «стоимость» и «вес» требуется отобрать...

Задача о рюкзаке - C++
Условие задачи:имеются m предметов с номерами от 0 до m-1, для каждого из которых известна масса и стоимость. Определить какие предметы...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
#pragma
Временно недоступен
952 / 223 / 6
Регистрация: 12.04.2009
Сообщений: 921
15.12.2009, 20:17 #2
А при чём тут траектории? Вы пытаетесь решить задачу об оптимальных путях?
0
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) - вот так.

Да, задача об оптимальном пути.
1
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
15.12.2009, 20:26
Привет! Вот еще темы с ответами:

Задача о рюкзаке 0-1 - C++
Здравствуйте! Есть задача о ранце, где даны вес и ценность каждого предмета, а также общая вместимость ранца. Нужно найти максимальную...

Вычислить нужную комбинацию. Задача о рюкзаке - C++
Добрый день форумчане! Немного завтыкал со сроками сдачи (ну как всегда), и в этот раз не уверен, что успею решить сам. Задача...

Задача о рюкзаке, решается ли она жадным алгоритмом? - C++
Здравствуйте. Задали сделать задачу о рюкзаке, используя жадину. Даны вес и стоимость предметов. Набить рюкзак предметами, чтобы...

Задача о рюкзаке методом полного перебора. Нужно пояснение по коду - C++
Здравствуйте, нужно пояснение по этому коду. Код не мой, также в нем много ошибок. Заранее спасибо. #include &lt;memory.h&gt; #include...


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

Или воспользуйтесь поиском по форуму:
Ответ Создать тему
Опции темы

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