Link to the problem on UVa Online Judge
For this problem we have to calculate the minimum price of buying at least K cooking oils. Whenever a problem asks you to calculate minimum or maximum of something, one possible approach is to think about optimizations and dynamic programming.
If you have solved some coin change challenges before, understanding the main approach to this problem won't be that hard for you.
I define the state of dynamic programming to be
f(n) : the minimum price we have to pay to buy exactly n cooking oils.
The recurrent formula would be something like this:
f(n) = min( pack_price[h] + f(n - pack_count[k]) : for all possible packs
What are the basic steps?
f(0) = zero, because buying no cooking oils needs zero dollars.
f(m) = INFINITY for m < 0, because negative m is invalid we return INFINITY to prevent using an invalid subproblem answer.
After calculating f(n) for each n, the answer of the problem is not f(n), actually you have to iterate starting at n and find some n greater than or equal to n which f(n) is minimum. For more detail look at the third sample case where you can buy 3 cooking oils for $40.00.
I had some problem reading input data, at first I read half of input using scanf and last line of each test with getline, then I changed it and read all input using getline and parse input myself.
For this problem we have to calculate the minimum price of buying at least K cooking oils. Whenever a problem asks you to calculate minimum or maximum of something, one possible approach is to think about optimizations and dynamic programming.
If you have solved some coin change challenges before, understanding the main approach to this problem won't be that hard for you.
I define the state of dynamic programming to be
f(n) : the minimum price we have to pay to buy exactly n cooking oils.
The recurrent formula would be something like this:
f(n) = min( pack_price[h] + f(n - pack_count[k]) : for all possible packs
What are the basic steps?
f(0) = zero, because buying no cooking oils needs zero dollars.
f(m) = INFINITY for m < 0, because negative m is invalid we return INFINITY to prevent using an invalid subproblem answer.
After calculating f(n) for each n, the answer of the problem is not f(n), actually you have to iterate starting at n and find some n greater than or equal to n which f(n) is minimum. For more detail look at the third sample case where you can buy 3 cooking oils for $40.00.
I had some problem reading input data, at first I read half of input using scanf and last line of each test with getline, then I changed it and read all input using getline and parse input myself.
No comments:
Post a Comment