6. Путёвки

 

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

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

 

Вход. Первая строка содержит количество путёвок n. Каждая из следующих n строк содержит два числа – количество дней dk и стоимость дня ck.

 

Выход. Максимальная сумма прибыли.

 

Пример входа

Пример выхода

4

2 37

3 45

1 46

4 30

232

 

 

РЕШЕНИЕ

перебор

 

Анализ алгоритма

Поскольку количество путевок n < 15 не велико, совершим полный перебор порядка их реализации и найдем тот порядок, при котором достигается наибольшая сумма прибыли.

 

Реализация алгоритма

Количество дней, которое осталось i-ой путевке, будем хранить в ячейке d[i]. В ячейке cost[i][day] будет содержаться стоимость i-ой путевки, если она будет реализована через i (i ≥ 0) дней после 1 февраля.

 

int d[16], used[16];

int cost[16][31];

 

Читаем входные данные. Стоимость дня ci для i-ой путевки будет храниться в cost[i][d[i] – 1], так как ее стоимость именно через d[i] – 1 дней будет равна ci.

 

scanf("%d",&n);

for(res = i = 0; i < n; i++)

  scanf("%d",&d[i]),scanf("%d",&cost[i][d[i] - 1]);

 

Стоимость i-ой путевки через j дней будет больше чем ее стоимость через j + 1 день на величину ci = cost[i][d[i] – 1]. Заполняем массив cost[i][day].

 

for(i = 0; i < n; i++)

{

  for(j = d[i] - 2; j >= 0; j--) 

    cost[i][j] = cost[i][j+1] + cost[i][d[i] - 1];

}

 

Запускаем перебор порядка реализации путевок. Ячейка used[i] = 0, если i-ая путевка еще не была реализована.

 

memset(used,0,sizeof(used));

go(0,0);

 

Выводим результат.

 

printf("%d\n",res);

 

Функция перебора go имеет два параметра: количество дней day, которое прошло после 1 февраля и текущая сумма, вырученная за продажу путевок за предыдущие day дней.

 

void go(int day, int sum)

{

  int i;

 

Вычисляем максимальную возможную сумму продаж путевок res. Она не обязательно достигается при day = n, так как мы не будем рассматривать при переборе путевки с нулевой стоимостью.

 

  if (sum > res) res = sum;

  if (day == n) return;

 

  for(i = 0; i < n; i++)

  {

 

Если i-ая путевка  еще не была продана (used[i] = 0) и ее стоимость за оставшиеся дни не нулевая, то реализовываем ее (включаем ее в перебор). Тот факт, что мы не рассматриваем путевки с нулевой стоимостью, значительно сокращает перебор.

 

    if (!used[i] && cost[i][day])

    {

      used[i] = 1;

      go(day+1, sum + cost[i][day]);

      used[i] = 0;

    }

  }

}