Помогите разобраться с алгоритмом для задачи. Есть n видов ценных бумаг. Причем бумаг i-ого вида w_i единиц. За продажу $%w_i$% единиц бумаг i-го вида можно получить прибыль $%p_i$%. Но в портфель можно взять не более W единиц ценных бумаг. В портфель можно брать любое количество ценных бумаг i-го вида, но не более $%w_i$% (прибыль пересчитывается). Нужно собрать портфель акций с максимальной стоимостью.

задан 14 Май '16 23:44

изменен 14 Май '16 23:45

А что если просто брать самые ценные из бумаг на каждом из шагов? То есть мы просто упорядочиваем по убыванию числа вида p_i/w_i, повторяя каждое в количестве w_i штук, и отрезаем от начала W из них (или берём всё, если количество позволяет).

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

(14 Май '16 23:53) falcao

Обычная "задача о ранце"... методами динамического программирования решается на раз...

(15 Май '16 13:55) all_exist

@all_exist: по-моему, здесь даже динамического программирования не надо (если я правильно понял условие). Просто берётся наибольшие числа.

(15 Май '16 15:24) falcao

@falcao, предлагаемый вариант решения даёт только приближённое решение... хотя я не знаю, что требуется ТС...

(15 Май '16 17:50) all_exist
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×245

задан
14 Май '16 23:44

показан
606 раз

обновлен
15 Май '16 17:50

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru