Take the 2-minute tour ×

I am trying to solve this problem from SPOJ, it's a dynamic programming problem, but I'm having trouble visualizing the recursive step. I believe it's similar to a knapsack, but here there are two constraints of Oxygen and Nitrogen.

Here is the link: http://www.spoj.pl/problems/SCUBADIV/

share|improve this question
So, what is your question? What have you tried? –  Mat Jul 27 '11 at 19:00
add comment

2 Answers

up vote 4 down vote accepted

This should work I think:

dp[i, j] = minimum weight needed such that we have i litres of oxygen and j litres 
           of nitrogen

dp[0, 0] = 0 and inf everywhere else
for each read cylinder k do
  for i = maxTotalOxygen down to oxygen[k] do
    for j = maxTotalNitrogen down to nitrogen[k]  do
      dp[i, j] = min(dp[i, j],                                       <- do not take cylinder k
                     dp[i - oxygen[k], j - nitrogen[k]] + weight[k])  <- take cylinder k 

Answer is the minimum dp[i, j] such that i >= RequiredOxygen and j >= RequiredNitrogen.

Note that the for loops must go from the max down to the values of the current cylinder, otherwise you allow a cylinder to be used more than once.

The problem constraints are very small and I think this should work.

share|improve this answer
I don't understand why the loop must go downwards. It should have the same effect if it was increasing right? –  user866098 Jul 27 '11 at 19:20
@user866098 - no, if it is increasing, then if you use cylinder k in the computation of a certain [i, j], k could also have been used to compute [i - oxygen[k], j - oxygen[k]], so it means you use it twice for [i, j], which isn't allowed by the SPOJ problem (although a problem that does allow it is perfectly valid as well). –  IVlad Jul 27 '11 at 19:37
Thanks for your help! But I'm still not very clear. –  user866098 Jul 27 '11 at 20:02
@User866098 - try running it manually on a small test. If you use a certain cylinder x where oxygen[x] = 2 and nitrogen[x] = 4 to find dp[3, 5] for example, you might also use it to find dp[5, 9] if you go ascendingly in the for loops, which you don't want to, because it would mean you used it twice for dp[5, 9]. –  IVlad Jul 27 '11 at 20:48
Shouldn't the inital values be 0 instead of infinity? Because: dp[5, 9] = min(dp[5,9],dp[3, 5] + weight[k]). If dp[3, 5] is infinity initially, then inf + weight[k] will be wrong right? –  user866098 Jul 28 '11 at 5:31
show 5 more comments

@IVlad very nice answer, thank you :)

However there's a catch:

The following should be removed :

dp[oxygen[i], nitrogen[i]] = weight[i] for each cylinder i and inf otherwise

And use this instead :

dp[0][0] = 0 and inf otherwise

The former statement is not a valid base case because it allows cylinders to be used twice.

How ?

The invariant of the outermost loop is that at the N th iteration (of k), we try for every i,j to compute the minimum weight that can be achieved to obtain at least i oxygen and j nitrogen using only cylinders 1 to N (each one used once)

Consider the following test case where 2 oxygen and 2 nitrogen is required and we have 2 cylinders one with 1 ox 1 ni 1 weight, the other is 2 ox 2 ni 50 weight

2 2


1 1 1

2 2 50

The answer should be 50 simply because we can't use the 1st cylinder twice.

The base case that i claim wrong will fill d[1][1] = 1 before we even start the loops. Then the loop starts with k=0 (use first cylinder and see if it helps in any entry), then d[2][2] will equal d[2-1][2-1]+1 = d[1][1] + 1 = 2

The final answer will be 2 units of weight because 1st cylinder was used twice due to the base case and this is not correct.

share|improve this answer
add comment

Your Answer


