This my attempt on solving the google code jam problem. You may refer to the problem directly in this page http://code.google.com/codejam/contest/2418487/dashboard#s=p1
Just to make it easier, I will copy and paste the problem statement here
You will have to manage your energy carefully. You start the day full of energy - E joules of energy, to be precise. You know you can't go below zero joules, or you will drop from exhaustion. You can spend any non-negative, integer number of joules on each activity (you can spend zero, if you feel lazy), and after each activity you will regain R joules of energy. No matter how lazy you are, however, you cannot have more than E joules of energy at any time; any extra energy you would regain past that point is wasted.
Now, some things (like solving Code Jam problems) are more important than others. For the ith activity, you have a value vi that expresses how important this activity is to you. The gain you get from each activity is the value of the activity, multiplied by the amount of energy you spent on the activity (in joules). You want to manage your energy so that your total gain will be as large as possible.
Note that you cannot reorder the activities in your calendar. You just have to manage your energy as well as you can with the calendar you have.
Since we cannot reorder the activity, we will need to go through each activity and try to maximize the amount of gain that we can get for that activity
The code below is in python
Few things I want to highlight here
This works for small data set but does not work for big data set :(.
Just to make it easier, I will copy and paste the problem statement here
Problem
You've got a very busy calendar today, full of important stuff to do. You worked hard to prepare and make sure all the activities don't overlap. Now it's morning, and you're worried that despite all of your enthusiasm, you won't have the energy to do all of this with full engagement.You will have to manage your energy carefully. You start the day full of energy - E joules of energy, to be precise. You know you can't go below zero joules, or you will drop from exhaustion. You can spend any non-negative, integer number of joules on each activity (you can spend zero, if you feel lazy), and after each activity you will regain R joules of energy. No matter how lazy you are, however, you cannot have more than E joules of energy at any time; any extra energy you would regain past that point is wasted.
Now, some things (like solving Code Jam problems) are more important than others. For the ith activity, you have a value vi that expresses how important this activity is to you. The gain you get from each activity is the value of the activity, multiplied by the amount of energy you spent on the activity (in joules). You want to manage your energy so that your total gain will be as large as possible.
Note that you cannot reorder the activities in your calendar. You just have to manage your energy as well as you can with the calendar you have.
Input
The first line of the input gives the number of test cases, T. T test cases follow. Each test case is described by two lines. The first contains three integers: E, the maximum (and initial) amount of energy, R, the amount you regain after each activity, and N, the number of activities planned for the day. The second line contains N integers vi, describing the values of the activities you have planned for today.Output
For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1) and y is the maximum gain you can achieve by managing your energy that day.Solution
It took me some time to figure out the problem but one thing I was sure this is a DP(Dynamic Problem) as the question requires us to maximize the amount of gain that we can get.Since we cannot reorder the activity, we will need to go through each activity and try to maximize the amount of gain that we can get for that activity
The code below is in python
Few things I want to highlight here
- Base case is end of task list
- We are given initial energy that we start with
- The maximum energy allowed cannot exceed the initial energy (that is what I am checking in line 11)
- Basically what I am doing here, is trying all possible energy I have available for a task. Using that I am calculating the gain I can get + the gain I can get from the next task (for the next task, I am subtracting of the energy I have used for this task + recharge energy)
- Simple memo (line 4). If I have calculated the maximum for this task and with that energy_available then I just return. The memo value is added in line 17
def calc_energy(init_energy,task,task_value,recharge,energy_avail,memo):
if task == len(task_value) : return 0
elif (task, energy_avail) in memo : return memo[(task, energy_avail)]
sol = []
for e in range(0, energy_avail + 1):
next_energy = (energy_avail - e) + recharge
if next_energy > init_energy : next_energy = init_energy
gain = e * task_value[task] + calc_energy(init_energy,task + 1, task_value,recharge,next_energy,memo)
sol.append(gain)
max_gain = max(sol)
memo[(task, energy_avail)]=max_gain
return max_gain
Test Case
print calc_energy(5,0,[2,1],2,5,{}) # 12
print calc_energy(5,0,[1,2],2,5,{}) # 12
print calc_energy(3,0,[4,1,3,5],3,3,{}) # 39
This works for small data set but does not work for big data set :(.
