Algorithm to Determine Maximum Fun

Question

The problem itself can be found here. The gist of it is that Bessie is riding a roller coaster, but she gets dizzy. What is the maximum amount of fun she can have without going over her "dizzy limit." The input consists of:

"N K L

where N (1 ≤ N ≤ 1,000) is the number of sections in this particular the roller coaster; K (1 ≤ K ≤ 500) is the amount that Bessies dizziness level will go down if she keeps her eyes closed on any section of the ride; and L (1 ≤ L ≤ 300,000) is the limit of dizziness that Bessie can tolerate — if her dizziness ever becomes larger than L, Bessie will get sick, and thats not fun!

Each of the next N lines will have two integers:

F D

where F (1 ≤ F ≤ 20) is the increase to Bessies total fun that shell get if she keeps her eyes open on that section, and D (1 ≤ D ≤ 500) is the increase to her dizziness level if she keeps her eyes open on that section. The sections will be listed in order."

My algorithm to solve this looks like this:

        cin >> N; // sections
        cin >> K; // amount dizziness can go down
        cin >> L; // dizzy ceiling
        belowL = L; // sets the amount of dizzy left

        for (int i = 0; i < N; i++) {
            cout << "\n" << i;
            cin >> F >> D; // fun increase and dizzy increase
            if (D < belowL) {
                if (F >= D) {
                    funTotal += F;
                }
            }
            else {
                belowL -= K;
            }

However, this does not always yield the correct result. What is the problem? It should pick the fun option, unless it would put Bessie over the sickness threshold. Is there a better way to do that?

Answer 1

So rather than give you code here's a sort of explanation of the problem solution.

The basic approach is to solve using dynamic programming as this reduces to what's called a Knapsack problem. Think of it this way, her dizziness is how much she can carry in the sack at once and the fun is what she would like to maximize (compared to say the value of the "items" she carries in a sack). Now what we would like to do is get the most enjoyment out of the roller coaster (most value in the sack) without making her too dizzy (going over the "weight" limit on the sack).

So now you want to pick which parts she has her eyes open/closed (whether an item is in the sack or not). So an easy way to think of this is choose the maximum of both options. If she can keep her eyes open without going over the threshold or whether to just keep her eyes closed. But now the problem changes, you see if she keeps her eyes open her diziness threshold will decrease (easier to solve sub problems).

Using this information it becomes easy to adapt the knapsack solution to this problem without having to use backtracking or recursion.

The idea is to save all the previously solved subproblems in a matrix so that you can reuse the results instead of recalculating them each time. Note one trick you can use is that you only need the current row of the matrix and the previously solved one because the recurrence relation for knapsack only requires those entries :)

P.S I was in the regional where this problem was given and solved it, nice to see this problem again

Answer 2

It should pick the fun option, unless it would put Bessie over the sickness threshold. Is there a better way to do that?

The problem is that you're not maximizing the fun here, you're just preventing Bessie from getting sick. When you get to a section that would put her over the dizzy limit, you may be able to add more fun by backtracking and taking the not-fun option on some previous section. Say you've got input like this, in F D order:

1 400
5 450
10 25
18 75
20 400

Further, let's say that she's already near the dizzy limit when she hits the first section above. You could take the fun option on the first two sections and get a F increase of 6 and a D increase of 850. Maybe that puts her right at the limit. Now you have no choice but to take the not-fun option for subsequent sections. On the other hand, if you take the not-fun option for the first two sections, you can take the fun option for the next three and get an increase in F of 48 for a D increase of only 500.

Your current algorithm takes the fun option if the F:D ratio is greater than 1 and you have enough dizziness capacity left. That's reasonable, but not optimal. It's likely that no fixed ratio will give an optimal solution. Instead, you need to consider the benefit and cost of each option for each section.