2015 Jan Gold Problem 2 Moovie Mooving

Problem Statement

Farmer John's cows are having a movie night, and they are trying to decide which movies to watch. They have N movies (1 <= N <= 20) to choose from, each with a different duration in minutes. The cows want to watch as many movies as possible, and they have a total of L minutes (1 <= L <= 1000) to watch movies before they need to go to sleep.

Each movie has a "moo" factor, which is a positive integer representing the cows' enjoyment. The cows want to maximize the total "moo" factor of the movies they watch. However, they can only watch each movie once, and they cannot pause and continue movies later. If they start watching a movie, they have to finish it.

Help the cows decide which movies to watch to maximize their total "moo" factor without exceeding the available time.

Input

   Line 1: Two space-separated integers, N and L.
   Lines 2..N+1: Line i+1 contains two space-separated integers: the duration and the "moo" factor of movie i.

Output

   Line 1: A single integer representing the maximum total "moo" factor the cows can achieve.

Solution

We can solve this problem using dynamic programming. Let's create a table dp[i][j], where i represents the bitmask of watched movies and j represents the number of minutes remaining. The value at dp[i][j] is the maximum "moo" factor that can be achieved by watching the movies represented by bitmask i with j minutes remaining.

We start by initializing the table to all zeros. Then, for each movie, we iterate over all possible bitmasks and update the table accordingly:

for movie in range(N):
    duration, moo_factor = movie_info[movie]
    for bitmask in range(1 << N):
        if bitmask & (1 << movie) == 0: # If the movie is not watched yet
            for time_left in range(L + 1 - duration):
                new_bitmask = bitmask | (1 << movie)
                new_time_left = time_left + duration
                dp[new_bitmask][new_time_left] = max(dp[new_bitmask][new_time_left], dp[bitmask][time_left] + moo_factor)

Finally, we find the maximum "moo" factor achieved:

max_moo_factor = 0
for bitmask in range(1 << N):
    for time_left in range(L + 1):
        max_moo_factor = max(max_moo_factor, dp[bitmask][time_left])

The time complexity of this solution is O(N * L * 2^N). Since N is at most 20 and L is at most 1000, this solution is efficient enough to solve the problem within the given constraints.