Путевки

[Тамерлан Абилов]

Прошу помочь ломаю голову уже не могу((

Туристическая фирма не успела из-за больших морозов продать n (n < 15) путёвок на горнолыжные базы, срок действия которых уже наступил. С целью уменьшения убытков, было решено с 1 февраля все такие путёвки, которым осталось dk (dk ≤ 30) дней, продавать по номинальной стоимости – по сk (сk ≤ 100) грн за день только за те дни, что остались со дня продажи (k = 1..n).

На какую наибольшую сумму можно реализовать эти путёвки, если каждый день продавать по одной путёвке?

Пример входных данных
4
2 37
3 45
1 46
4 30
Пример выходных данных
232

на сайте есть такая задача.задачи оптимизации не проходил нема что это и как быть.всячески думаю алгоритм все равно не складывается(легче изучить теорию?а начал так:считаю прибыль или убыток от каждого проданного.с Примера же.продавая 1ый билет за день я потеряю:2*37- 45-46-30 грн..грубо говоря.и так я продаю же билет который имеет минимальный убыток.но тут все равно приоритет.если какому та 1му билету остался 1 день.и он же четко говоря дает мне прибыль за день.то все идет в кашу.потому что сперва надо продать его если не ошибся.не говоря уже что таких билетов может быть 2-3 и т.д. а тогда из них нужно выбрать один учитывая прибыль только с дк>1 билетов(те билеты которым осталось больше 1 дня) вот ломаю голова хз уже

пс. русским языком не владею хорошо)КРАТКО говоря есть ли алгоритм норм без этой оптимизации.или лучше оптимизация?спс за отзывы)Могу код кинуть но вряд ли там что то понятное все запутано(

[Poma][a]

Самый очевидный вариант будет работать долго, но железно.. полный перебор..

Чисто идейно..
Для начала надо брать те путевки, которые вскоре закончатся..
Тоесть : 5
3 10
3 11
3 12
100 10
100 10
Продаем сначала трехи..
Но если
5
3 11
3 12
3 13
100 10000
100 100000

То продаем 100, а затем одну треху...


Вообщем тут много есть над чем подумать..

[Тамерлан Абилов]

Ромаха. да я и об этом что шанс на то что ты продавая билеты столкнешься на 1 рку велик. а при первом варианте.есть условие которое и ты подтверждаешь,почти.если цена билетов которые закончатся больше чем(!) у других(у которых дней больше) то их надо продавать.а если нет то наоборот.а в твоем случае 3 10 или же 100 10 не имеет разницы а вот остальные тройки по ценам больше нижних,из них продаем тот который макс цена..но это когда дни почти равны. а если рандом чистый то мой алгоритм работает до случая,который ты подчеркнул. а по любому во многих случаях столкнется 1 рка допустим же
4
2 37
3 45
1 46
4 30
он дойдет до
1 37
3 30
то что я понаделал продам 3 30(прибыли якобы больше чем другой билет) .а на самом деле просто по твоему же принципу где сумма больше ту и продаешь)но и там есть подвох.короче думаю все же теорию знать надо((