Если для боя с боссом нужно 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. Ну и вторая идея, которая там есть. Если хвост безнадёжен, то меньшие хвосты безнадёжны и подавно.
Средний
Простой
