How to find the minimum time that satisfies the condition?

Question

Java

Help with the implementation please. Or at least point me in the right direction.
I will be very grateful. I can't think of an optimal algorithm. I don't know which way to go.

Answer 1

If the boss fight requires 0 points, we output 0.
If all the missions add up to <K points, we output “No”.
And if not, I don’t see anything yet, except for advanced enumeration.
Sort the missions by the ratio "points / time". The main thing is to correctly cut off the enumeration: for example, each time we linearly extrapolate the best available mission by the “points / time” ratio: will it be possible to fit in or not? Let's look at the sum of the "tail": is it possible to get K at all by summing the "tail"?

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;
}

Missions, as before, are sorted by ratio in ascending order.
And my last idea, which at times accelerated the enumeration, is as follows. The recursive function returns true if the entire allowed "tail" is hopeless and there is nothing more to look for in it. It happens under these conditions.
1. The tail is empty.
2. The tail is not enough to get K points.
3. The simplest extrapolation for the 1st mission failed.
4. Already the first recursive call says: the tail is hopeless.
UPD2. Well, the second idea, which is there. If the tail is hopeless, then the smaller tails are hopeless and even more so.

Answer 2

This is a paraphrase of the knapsack problem. It should only be noted that the optimal answer will score less than K + 100 points. Otherwise, you can painlessly throw out some mission (and they all take <100 seconds).
Solution by dynamic programming. I will not repeat here - it is simple and painted everywhere. Let me remind you once again of the keywords - "the knapsack problem".
Now the price of the item in the knapsack problem is the time, and the weight of the item is the points. Fill in DP[i] - the minimum time for which you can score i points. Then we look for the minimum on the interval [k..k+100). This is the answer to the problem.