PROBLEM LINKSDIFFICULTYSIMPLE PREREQUISITESDynamic Programming PROBLEMThere are N fuel stations numbered 1 through N. The ith fuel station can fill exactly K_{i} liters at any time. You have N days. On the ith day, you must have exactly 2 × H_{i} liters in your fuel tank. After that, you will have a round trip and the tank will become empty again. Determine the minimum number of times you must fill your fuel tank on the whole N days. QUICK EXPLANATIONUse dynamic programming approach. Let dp[i][j] = the minimum number of times to fill exactly j liters using only fuel stations 1 through i. The answer to the problem is dp[N][2 × H_{1}] + dp[N][2 × H_{2}] + ... dp[N][2 × H_{N}]. EXPLANATIONThis is problem can be reduced to the traditional coin change problem. We have N types of coin, each having value K_{1}, K_{2}, ..., and K_{N}. We want to make changes for N days, each for 2 × H_{1}, 2 × H_{2}, ..., and 2 × H_{N}. What is the minimum number of coins needed? Note that since each day is independent, we can minimize the number of coins on each day, and sum the results over N days. Mathematically, for each day i, we want to minimize the value of X_{1} + X_{2} + ... + X_{N} subject to
X_{1}K_{1} + X_{2}K_{2} + ... + X_{N}K_{N} = 2 × H_{i} We will use dynamic programming to solve this problem. Let dp[i][j] = the minimum number of coins needed to make changes for j, using only coins of types 1 through i. The base case is:
We can use a very large number such as 1,000,000,000 as infinity in our code. We need to setup a recurrence relation. For each state dp[i][j], there are two possibilities:
Therefore, we have dp[i][j] = min(dp[i  1][j], 1 + dp[i][j  K_{i}]) Both time and space complexity of this solution are in O(N × max{H_{i}}). Here is a pseudocode of this solution. read(N) for i = 1; i ≤ N; i++: read(H[i]) for i = 1; i ≤ N; i++: read(K[i]) dp[0][0] = 0 for j = 1; j ≤ max{2 × H[i]}; j++: dp[0][j] = 1000000000 for i = 1; i ≤ N; i++: for j = 0; j ≤ max{2 × H[i]}; j++: dp[i][j] = dp[i1][j] if K[i] ≤ j: dp[i][j] = min(dp[i][j], 1 + dp[i][jK[i]) int res = 0 for i = 1; i ≤ N; i++: res = res + dp[N][2*H[i]] println(res) There is a solution that only uses O(max{H_{i}}) memory for the dp table. This solution uses the facts that:
read(N) for i = 1; i ≤ N; i++: read(H[i]) for i = 1; i ≤ N; i++: read(K[i]) dp[0] = 0 for j = 1; j ≤ max{2 × H[i]}; j++: dp[j] = 1000000000 for i = 1; i ≤ N; i++: for j = K[i]; j < max{2 × H[i]}; j++: dp[j] = min(dp[j], 1 + dp[jK[i]) int res = 0 for i = 1; i ≤ N; i++: res = res + dp[2*H[i]] println(res) Note that for the ith row we fill the table from K[i] instead from 0. This is because for j < K[i] the DP values will not change. Another solution is to use the socalled "forward DP", i.e. filling the latter entries of the DP table using the values of the current entry. This is just a matter of style. read(N) for i = 1; i ≤ N; i++: read(H[i]) for i = 1; i ≤ N; i++: read(K[i]) dp[0] = 0 for j = 1; j ≤ max{2 × H[i]}; j++: dp[j] = 1000000000 for i = 1; i ≤ N; i++: for j = 0; j+K[i] < max{2 × H[i]}; j++: dp[j+K[i]] = min(dp[j+K[i]], 1 + dp[j]) int res = 0 for i = 1; i ≤ N; i++: res = res + dp[2*H[i]] println(res) In all solutions above, we do not remove duplicate coin types as they do not affect the answer, although they will make us recompute the same coin types in the DP table. SETTER'S SOLUTIONCan be found here. TESTER'S SOLUTIONCan be found here.
This question is marked "community wiki".
asked 11 Dec '12, 18:13

The O(max{H}) space approach is actually mincoin change problem. answered 11 Dec '12, 19:09

Can someone please tell me the recurrence tree of this problem.Thanks in advance. answered 28 Jun '14, 18:14

Hi I have tried a similar approach but I am getting WA. Please help me find out the error. Code is here answered 12 Dec '12, 10:21

I had figured out that it is identical to coin change problem. I had used the below approach.
for(int i=1; i<=size{H}; i++) { for(int j=1; j<=size{K}; j++) { if(K[j] == i) { opt[i] = 1; break; } else if(K[j] < i) { if((opt[i  K[j]] + 1) < opt[i]) { opt[i] = (opt[i  K[j]] + 1); } } } } The space complexity is O(H_max*2) and time complexity is O(size{K} * size{H}) answered 12 Dec '12, 20:52
1
Hmmm.. Surprisingly, just interchanging for loops as given in the solution section is getting AC. How does it makes a difference whether we iterate over {K}> {H} or {H}> {K}. Interesting and frustrating!!!
(12 Dec '12, 23:04)
@prakash1529 Maybe taking into account cache misses in the target system , your observation makes sense :)
(04 Nov '14, 15:21)

#include <iostream> #include <stdio.h> #include <algorithm> #include <string.h> using namespace std; int main() { int t; scanf("%d",&t); int H[501],K[501]; int N,max; while(t) { int dp[501][1001]; max=0; scanf("%d",&N); for(int i=1;i<=N;i++) { scanf("%d",&H[i]); if(max<h[i]) max="H[i];" }="" for(int="" i="1;i<=N;i++)" scanf("%d",&k[i]);="" dp[0][0]="0;" for(int="" j="1;j<=max*2;j++)" dp[0][j]="1000000000;" for(int="" i="1;i<=N;i++)" {="" for(int="" j="0;j<=2*max;j++)" {="" dp[i][j]="dp[i1][j];" if(k[i]<="j)" dp[i][j]="min(dp[i][j],1+dp[i][jK[i]]);" }="" }="" int="" sum="0;" for(int="" i="1;i<=N;i++){" sum="sum+dp[N][2*H[i]];" }="" printf("%d",sum);="" }="" your="" code="" goes="" here="" return="" 0;="" }="" <code=""> why my answer is giving WA pls help answered 26 Jul '14, 18:13

The approach I have taken is like this. Using a bottom up approach, we can build a solution.
answered 04 Nov '14, 15:12

I know its a very old question but I was trying it as a practice and noticed a strange thing: Going by the for loops as in the solution setting give AC. But interchanging the order of for loops gives wrong answer. Any one who can throw some more light? @betista's solution and @prakash1529's comment also highlights the same phenomenon. Any pointers to this mistery? answered 22 Dec '14, 00:02

can anyone tell me what's wrong with my code? here's my code https://www.codechef.com/viewsolution/7606972 answered 02 Aug '15, 11:14
