I am facing problems solving this question and cannot find an appropriate approach towards it. The problem is as follows:

A tourist visits Switzerland for a two day trip and landed there on Friday. As he has to return back on Monday, so he gets to spend the weekend in Switzerland. There are many things one can do in Switzerland in 2 days ..

1. Visit Matterhorn (1/2 a day gone) : rating is 7
2. Visit Jungfraujoch (1 day gone) : rating is 9
3. Visit the Interlaken (1/2 day) : Rating is 6
4. Shopping (Montreux) for all 2 days : Rating is 9
5. Lucerne : 1/2 day : Rating is 8

What places should you visit, where you can visit as per maximum ratings, given your time constraints (is provided as 2 days) ?

Input :

int val[] = { 7, 9, 6, 9, 8 };
float timeLeft[] = { 0.5f, 1f, 0.5f, 2f, 0.5 f};

O/P -

 1. (Maximum rating as specified by overall time ) : 24 
 2. places you need to visit to achieve it in that time frame like : Lucerne , Matterhorn , Jungfraujoch

Explanation : As with time constraint, here provided as 2 days which is only 48 hours. so as far as rating goes, with, Lucerne(8) Matterhorn(7) Jungfraujoch(9) = 24 will be apt [since Jungfraujoch is 1 day as per time needed to visit).

CodePudding user response：

You need to use dynamic programming for this:

public class BestTwoDayTrip {
    public static void main(String[] args) {
        int val[] = { 7, 9, 6, 9, 8 };
        float timeLeft[] = { 0.5f, 1f, 0.5f, 2f, 0.5f};

        System.out.println(getMaxValue(val, timeLeft, 2, 0));
    }

    private static int getMaxValue(int[] val, float[] timeLeft, float numberOfDays, int valIndex) {
        if (numberOfDays == 0) return 0;
        int max = 0;
        for (int i = valIndex; i < val.length; i  ) {
            if (numberOfDays >= timeLeft[i]) {
                int localMax = val[i]   getMaxValue(val,
                        timeLeft,
                        numberOfDays - timeLeft[i],
                        i   1);
                max = Math.max(max, localMax);
            }
        }
        return max;
    }
}

You can also avoid recursion by using a queue or stack.

CodePudding user response：

Each place has

• a given "rating" (analogous to it's value)
• a given "time" required (analogous to the weight/cost you pay for the place).

You need to pick places to give the maximum value with a weight constraint (of 2 days in your problem).
This directly translates into the 0-1 Knapsack Problem, which is pretty straightforward dynamic programming problem with multiple possible solutions.