Its been over 7 days since i have asked a question of spoj on the codechef forum
I ask again please explain me the approach of this problem
Its been over 7 days since i have asked a question of spoj on the codechef forum
I ask again please explain me the approach of this problem
Let us represent dp[i][j][k] as minimum cylinders required from first βkβ cylinders such that we have βiβ litres of Oxygen and βjβ litres of Nitrogen. Itβs clear that :
dp[0][0][k] = 0 ,0<=k< Number of Cylinders and we initialize
dp[i][j][0]=infinite (say 999999) ,0<=i< Total litres of Oxygen and 0<=j< Total litres of Nitrogen
Now we can have some thing like this :
part1=dp[i][j][k-1] // Not considering k th cylinder
part2=dp**[max( 0 , i-Oxygen[k] )]** [max( 0 , j-Nitrogen[k] )] [k-1]+Cylinder[k] // Consider k th cylinder
dp[i][j][k] = min(part1,part2)
Here Oxygen[k],Nitrogen[k],Cylinder[k] represents volume of oxygen and nitrogen in the k-th cylinder and the weight of that cylinder.
Iterate over all cylinders and over all possible amounts of Oxygen and Nitrogen
Now Required answer is minimum of dp[i][j][k] such that i>=Required amount of Oxygen and j>=Required amount of Nitrogen
If you can not get this approach try solving manually with the given test cases using this approach and still if you did not get
I guess it would be helpful first if you understand/try 0-1 knapsack as this problem is a slightly extension of it