Link to pdf version on UVa OJ
What happened on my mind : After reading the problem statement, first I tried to come up with some greedy solutions, for making it minimum I think there is a greedy solution, but for maximizing I couldn't find any greedy approach, then I realized for maximizing it we need to check all different possible states. Then I tried to write the abstract of the problem. (abstract of the problem is the version you explain to your teammate and remove all the extra information)
Abstract version: we have n+m numbers and we want to divide them into two groups that multiplication of sum of them becomes maximum(minimum).
Then I looked at the range of numbers -50 to 50. The number of integers is at most 100. Previously I realized I have to check all possible sums for one group and try to find the maximum.
So here is the final version I came up with, can I make sum out of n+m numbers by choosing n of them? Isn't this the state for the dynamic programming solution?
bool f(int index, int remain, int sum) : this means I have access to the first index numbers, I have to take exactly remain numbers of them and make sum with that.
Another tip for finding out whether to try Dynamic Programming solution is the fact that we have option, we have to choose for each element whether to give it to the first group or to the second group.
f(index, remain, sum) = f(index-1, remain, sum) OR f(index-1, remain-1, sum - coin[index])
This is the recursion formula. As you see the problem was reduced to coin change problem : We have n+m coins, we want to take n coins of them, can we make sum with them?
The base case is f(0, 0, 0) which is true, we have zero coins, we want to take zero of them, can we make sum of zero? Yes, take nothing and make zero :D.
I explained the top-down solution here, but in my code I solved it using a bottom-up approach, because I was afraid of the number of subproblems (states), and the recursion overhead.
For more details refer to my own solution on github.
What happened on my mind : After reading the problem statement, first I tried to come up with some greedy solutions, for making it minimum I think there is a greedy solution, but for maximizing I couldn't find any greedy approach, then I realized for maximizing it we need to check all different possible states. Then I tried to write the abstract of the problem. (abstract of the problem is the version you explain to your teammate and remove all the extra information)
Abstract version: we have n+m numbers and we want to divide them into two groups that multiplication of sum of them becomes maximum(minimum).
Then I looked at the range of numbers -50 to 50. The number of integers is at most 100. Previously I realized I have to check all possible sums for one group and try to find the maximum.
So here is the final version I came up with, can I make sum out of n+m numbers by choosing n of them? Isn't this the state for the dynamic programming solution?
bool f(int index, int remain, int sum) : this means I have access to the first index numbers, I have to take exactly remain numbers of them and make sum with that.
Another tip for finding out whether to try Dynamic Programming solution is the fact that we have option, we have to choose for each element whether to give it to the first group or to the second group.
f(index, remain, sum) = f(index-1, remain, sum) OR f(index-1, remain-1, sum - coin[index])
This is the recursion formula. As you see the problem was reduced to coin change problem : We have n+m coins, we want to take n coins of them, can we make sum with them?
The base case is f(0, 0, 0) which is true, we have zero coins, we want to take zero of them, can we make sum of zero? Yes, take nothing and make zero :D.
I explained the top-down solution here, but in my code I solved it using a bottom-up approach, because I was afraid of the number of subproblems (states), and the recursion overhead.
For more details refer to my own solution on github.
No comments:
Post a Comment