Ошибка жадного алгоритма при использовании наборов c ++

Я создал жадный алгоритм для решения проблемы (домашнее задание), и так как я учусь c++ Я хотел бы добиться того же, но используя sets,

По сути, мы передаем домашнее задание на онлайн-платформу, которая представляет собой несколько тестовых примеров, о которых мы не знаем, и на основании этого мы получаем оценку. Если мы пройдем все тесты, у нас будет 100%;

Проблема в этом.

У нас есть актер, который хочет запланировать встречи с поклонниками, которые ответили на онлайн-анкету о нем. Теперь он хочет выбрать фанатов, которые максимизируют сумму баллов в вопроснике и учитывают доступность фанатов. Он может видеть только одного поклонника в день.

У нас есть такой вклад:

6
1 1 5
2 2 4
3 1 2
4 3 1
5 1 6
6 2 2

Если в первой строке указано количество поклонников, а в каждой строке указывается идентификатор поклонника, число дней, в которые он был доступен, и баллы, полученные в онлайн-вопроснике. Я должен напечатать идентификаторы фанатов, которые увидит актер, и сумму комбинированных баллов фанатов. Таким образом, для вышеуказанного ввода у меня есть следующий вывод:

2
4
5
11

Обратите внимание, что если два вентилятора имеют одинаковые точки, предпочтительным должен быть вентилятор с более низким ID.

Я начал с сортировки поклонников по пунктам анкеты (в порядке убывания), а затем по нижнему идентификатору.
При чтении ввода я добавляю количество дней к set,
Моя идея была такой:

Перебирая данные, я проверяю, находится ли фанат в доступные учебные дни в set, Если это так, добавьте этот вентилятор и удалите дни из набора. Если фанатских дней нет в наборе, то получите upper_bound и уменьшите итератор, чтобы установить вентилятор в первый день ниже, чем начальный день. Алгоритм останавливается, когда набор пуст или я перебираю вентиляторы.

Вот моя жадная функция:

void greedy() {
fan_id.insert(questionnaire_result[0][0]);
days_available.erase(questionnaire_result[0][1]);
total_questionaire_sum += questionnaire_result[0][2];

int i;
for (i = 1; i < number_of_fans; i++) {
if (days_available.empty()) {
break;
} else if (days_available.count(questionnaire_result[i][1])) {
fan_id.insert(questionnaire_result[i][0]);
days_available.erase(questionnaire_result[i][1]);
total_questionaire_sum += questionnaire_result[i][2];
} else {
it = days_available.upper_bound(questionnaire_result[i][1]);
if (it == days_available.begin()) {
if (*it < questionnaire_result[i][1]) {
fan_id.insert(questionnaire_result[i][0]);
days_available.erase(*it);
total_questionaire_sum += questionnaire_result[i][2];
}
} else if (it == days_available.end()) {
it--;
if (*it < questionnaire_result[i][1]) {
fan_id.insert(questionnaire_result[i][0]);
days_available.erase(*it);
total_questionaire_sum += questionnaire_result[i][2];
}

} else {
it--;
if (*it < questionnaire_result[i][1]) {
fan_id.insert(questionnaire_result[i][0]);
days_available.erase(*it);
total_questionaire_sum += questionnaire_result[i][2];
}
}
}
}
}

Я считаю, что моя проблема в этой строке:

it = days_available.upper_bound(questionnaire_result[i][1]);

Я протестировал много возможностей, и это работает во всех моих тестовых случаях. К сожалению, у нас нет тестовых примеров платформы.

Кто-нибудь видит ситуацию, когда мой код не работает? При этом я получаю 90% баллов.

РЕДАКТИРОВАТЬ:

Как указал мне Эдвард, мне удалось решить проблему следующим образом:

При чтении ввода добавляется эта строка кода:

max_days = max_days | questionnaire_result[i][1];

А потом сделал это:

for (int j = 1; j < max_days + 1; j++) {
days_available.insert(j);
}

Задача решена

0

Решение

Этот входной файл приведет к тому, что программа выдаст неверный результат:

2
1 2 6
2 2 5

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

1

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]