 Its been over 7 days since i have asked a question of spoj on the codechef forum

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[k] = 0 ,0<=k< Number of Cylinders and we initialize

dp[i][j]=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

http://en.wikipedia.org/wiki/Knapsack_problem

http://www.spoj.com/problems/KNAPSACK/

2 Likes