@Catzy

Как найти минимальное время которое удовлетворяет условие?

3d290de218cc4ed8bdcf63d9f277e8b4.PNG

Помогите с реализацией пожалуйста. Или хоть натолкните в нужном направлении.
Буду очень благодарен. Немогу придумать оптимальный алгоритм. Не знаю с какой стороны подойти.
  • Вопрос задан
  • 785 просмотров
Решения вопроса 1
@Mercury13
Программист на «си с крестами» и не только
Если для боя с боссом нужно 0 очков — выводим 0.
Если все миссии в сумме дают <K очков — выводим «Нельзя».
А если нет — ничего пока не вижу, кроме продвинутого перебора.

Сортируем миссии по соотношению «очки/время». Главное — правильно отсечь перебор: например, каждый раз линейно экстраполируем по соотношению «очки/время» лучшей доступной миссии: удастся вписаться или нет? Смотрим на сумму «хвоста»: можно ли вообще, просуммировав «хвост», получить K?
int N, K;
Mission missions[100];
int bestTime = std::numeric_limits<int>::max();

bool recurse(int firstMission, int currPoints, int currTime)
{
    if (currTime >= bestTime)
        return false;
    if (currPoints >= K) {
        bestTime = currTime;
        return false;
    }
    if (firstMission >= N)
        return true;

    int remPoints = K - currPoints;

    for (int i = firstMission; i <= N; ++i) {
        bool isFirst = (i == firstMission);
        const Mission& im = missions[i];
        if (currPoints + im.tailPoints < K)           // tailPoints = сумма очков по хвосту от missions[i] до конца
            return isFirst;
        float wantedTime = currTime + remPoints * im.ratio;    // ratio = (float)m.time / m.points;
        if (wantedTime >= bestTime)
            return isFirst;
        if (recurse(i + 1, currPoints + im.points, currTime + im.time))
            return isFirst;
    }
    return false;
}

Миссии, как и раньше, отсортированы по ratio по возрастанию.

И последняя моя идея, в разы ускорившая перебор, такова. Рекурсивная функция возвращает true, если весь разрешённый «хвост» безнадёжен и в нём искать больше нечего. Это происходит при таких условиях.
1. Хвост пуст.
2. Хвоста недостаточно, чтобы получить K очков.
3. Простейшая экстраполяция по 1-й миссии провалилась.
4. Уже первый рекурсивный вызов говорит: хвост безнадёжен.

UPD2. Ну и вторая идея, которая там есть. Если хвост безнадёжен, то меньшие хвосты безнадёжны и подавно.
Ответ написан
Пригласить эксперта
Ответы на вопрос 1
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Это перефразированная задача о рюкзаке. Надо только заметить, что в оптимальном ответе будет набрано менее K+100 очков. Иначе можно безболезненно выкинуть какую-нибудь миссию (а они все <100 секунд занимают).

Решение динамическим программированием. Не буду тут повторять - оно простое и везде расписано. Еще раз напомню ключевые слова - "задача о рюкзаке".
Теперь цена предмета в задаче о рюкзаке - это время, а вес предмета - это очки. Заполняем DP[i] - минимальное время за которое можно набрать i очков. Потом ищем минимум на отрезке [k..k+100). Это и есть ответ к задаче.
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
Bell Integrator Ульяновск
До 400 000 ₽
Bell Integrator Ижевск
До 400 000 ₽
Bell Integrator Хабаровск
До 400 000 ₽