перебор с отсечениями | C++ для приматов

Постановка задачи

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

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

Входные данные

Первая строка содержит количество путёвок [latex]n[/latex]. Каждая из следующих [latex]n[/latex] строк содержит два числа – количество дней [latex]d_k[/latex] и стоимость дня [latex]c_k[/latex].

Выходные данные

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

Алгоритм решения

Решим эту задачу полным перебором (методом грубой силы). Для этого необходимо перебрать все возможные варианты реализации. К примеру, дано три путевки:

Первая путёвка

срок действия: 2
номинальная стоимость: 13

Вторая путёвка

срок действия: 1
номинальная стоимость: 33

Третья путёвка

срок действия: 3
номинальная стоимость: 7

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

Путевки	Перебор всех возможных вариантов
	Вариант 1		Вариант 2
	Очередность	Результат	Очередность	Результат
Первая	1	20	1	20
Вторая	2		3
Третья	3		2
	Вариант 3		Вариант 4
	Очередность	Результат	Очередность	Результат
Первая	2	53	2	20
Вторая	1		3
Третья	3		1
	Вариант 5		Вариант 6
	Очередность	Результат	Очередность	Результат
Первая	3	40	3	7
Вторая	1		2
Третья	2		1

Теперь очевидно, что максимальная сумма прибыли равна 53. Таким образом можно решить данную задачу при любых входных данных. Но возникает проблема, когда путевок слишком много (или даже не очень). Количество перестановок для [latex]n[/latex] элементов равно [latex]n![/latex]. Это значит, что при количестве путевок, равном [latex]14[/latex] (максимальное возможное количество в данной задаче), количество перестановок равно [latex]14! = 87178291200[/latex], а ведь для каждой необходимо подсчитать сумму за реализованые путевки. Современные компьютеры не могут справиться с этой задачей за короткий промежуток времени, поэтому явным решением является оптимизация программы.

Давайте представим, что мы имеем две путевки, сроки действия которых равны единице. Очевидно, что одну из них мы точно не успеем реализовать, так как продав одну, срок действия другой на следующий день истечет, а, так как реализовать путевки необходимо за наибольшую сумму, то реализовать нужно ту, чья номинальная стоимость выше. Отсюда следует, что, когда есть две путевки, сроки действия которых равны единице, более дешевую можно игнорировать. Теперь, пусть у нас есть три путевки, сроки действия которых равны двум. Аналогично рассуждая, можно прийти к выводу, что в такой ситуации путевку с самой низкой номинальной стоимостью можно игнорировать. Это же верно для четырех, пяти и т.д. путевок. Тогда нам остается перед началом полного перебора отсечь путевки, не влияющие на ответ, при этом сократив время выполнения в разы.

Тесты

Входные данные	Выходные данные
4 2 37 3 45 1 46 4 30	232
3 1 1 2 2 3 3	11
4 1 2 3 4 5 6 7 8	84

Реализация

ideone: ссылка
Засчитаное решение: ссылка

#include <iostream>
#include <algorithm>
using namespace std;

struct ticket {
	int id, validity, price;
};

int cutDown(ticket tickets[], int count) {
	for(int validity = 0; validity <= min(30, count - 1); validity++) {
		int ticketsCount = 0;
		for(int i = 0; i < count; i++) {
			if(tickets[i].validity == validity) {
				ticketsCount++;
			}
		}
		while(ticketsCount > validity) {
			int cheapestTicketPosition = -1;
			int cheapestTicketPrice = 101;
			for(int i = 0; i < count; i++) {
				if(tickets[i].validity == validity && tickets[i].price < cheapestTicketPrice) {
					cheapestTicketPrice = tickets[i].price;
					cheapestTicketPosition = i;
				}
			}
			tickets[cheapestTicketPosition] = tickets[--count];
			ticketsCount--;
		}
	}
	return count;
}

bool comparator(const ticket t1, const ticket t2) {
	return t1.id < t2.id;
}

int main() {
	int count;
	cin >> count;
	ticket tickets[count];
	for(int i = 0; i < count; i++) {
		tickets[i].id = i;
		cin >> tickets[i].validity >> tickets[i].price;
	}
	count = cutDown(tickets, count);
	sort(tickets, tickets + count, comparator);
	int maxProfit = 0;
	do {
		int profit = 0;
		for(int i = 0; i < count; i++) {
			profit += tickets[i].validity > i ? tickets[i].price * (tickets[i].validity - i) : 0;
		}
		maxProfit = max(profit, maxProfit);
	} while(next_permutation(tickets, tickets + count, comparator));
	cout << maxProfit << endl;
	return 0;
}

#include <iostream>

#include <algorithm>

using namespace std;

struct ticket {

int id, validity, price;

};

int cutDown(ticket tickets[], int count) {

for(int validity = 0; validity <= min(30, count - 1); validity++) {

int ticketsCount = 0;

for(int i = 0; i < count; i++) {

if(tickets[i].validity == validity) {

ticketsCount++;

}

while(ticketsCount > validity) {

int cheapestTicketPosition = -1;

int cheapestTicketPrice = 101;

for(int i = 0; i < count; i++) {

if(tickets[i].validity == validity && tickets[i].price < cheapestTicketPrice) {

cheapestTicketPrice = tickets[i].price;

cheapestTicketPosition = i;

}

tickets[cheapestTicketPosition] = tickets[--count];

ticketsCount--;

}

return count;

}

bool comparator(const ticket t1, const ticket t2) {

return t1.id < t2.id;

}

int main() {

int count;

cin >> count;

ticket tickets[count];

for(int i = 0; i < count; i++) {

tickets[i].id = i;

cin >> tickets[i].validity >> tickets[i].price;

}

count = cutDown(tickets, count);

sort(tickets, tickets + count, comparator);

int maxProfit = 0;

do {

int profit = 0;

for(int i = 0; i < count; i++) {

profit += tickets[i].validity > i ? tickets[i].price * (tickets[i].validity - i) : 0;

}

maxProfit = max(profit, maxProfit);

} while(next_permutation(tickets, tickets + count, comparator));

cout << maxProfit << endl;

return 0;

}

Related Images:

Задача о восьми мирных ладьях

Условие

Получить все расстановки [latex]8[/latex] ладей на шахматной доске, при которых ни одна ладья не угрожает другой.

Решение

Для начала, выясним, а сколько существует таких расстановок, при условии, что рассматривается стандартная шахматная доска [latex]8 \times 8[/latex].

Ладья находится под боем, если другая ладья находится с ней на одной строке или в одном столбце. Следовательно, фиксируя, скажем, столбцы, можно разместить ладьи по строкам таким образом, чтобы ни одна пара не находилась под боем.

Заведем массив на восемь элементов и занумеруем его таким образом, чтобы значение [latex]j[/latex] по индексу [latex]i[/latex] соответствовало строке [ [latex]j[/latex], в которой находится ладья в [latex]i[/latex]-м столбце.

Теперь легко видеть, что положение на доске определяется перестановкой чисел [latex]1,..,8[/latex]. Как известно, число различных перестановок длины [latex]n[/latex] — [latex]P_{n}=n![/latex]. Следовательно, всего существует [latex]8!=40320[/latex] различных расстановок ладей.

Реализация
ideone: http://ideone.com/tBySY4
Легенда: R — Rook — ладья

#include <cstdio>
#include <algorithm>
using namespace std;

int state[8] = {0, 1, 2, 3, 4, 5, 6, 7};
int main()
{
    do{
        for(int i = 0; i < 8; i++){
            for(int j = 0; j < 8; j++)
                printf("%c ", (state[i] == j ? 'R' : '#'));
            printf("\n");
        }
        printf("\n");
    } while(next_permutation(state, state+8));
    return 0;
}