Catzy

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