Dynamic programming SPOJ problem SCUBADIV

Question

I am trying to solve this problem from SPOJ, it is a dynamic programming problem, but I am having problems visualizing a recursive step. I think it looks like a backpack, but there are two restrictions on oxygen and nitrogen.

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

Answer 1

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. 

Please note that for loops must go from max to the values ​​of the current cylinder, otherwise you can use the cylinder more than once.

The limitations of the problem are very small, and I think it should work.

Answer 2

@IVlad is a very good answer, thanks :)

However, there is a catch:

You must remove the following:

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

And use instead:

 dp[0][0] = 0 and infinity everywhere else 

The first statement is not a valid base case, because it allows you to use cylinders twice.

How?

The invariant of the outermost cycle is that at the Nth iteration (k), we will try for each i, j to calculate the minimum weight that can be achieved to obtain at least oxygen and j nitrogen , using only cylinders from 1 to N (each of them is used once)

Consider the following test example, in which 2 oxygen and 2 nitrogen are required, and we have 2 cylinders with 1 weight 1 weight 1, the other 2 ox 2 ni 50 weight.

2 2

2

1 1 1

2 2 50

The answer should be 50 simply because we cannot use the 1st cylinder twice.

The base case, which I require incorrectly, will fill in d [1] [1] = 1 before we even start the loops. Then the cycle starts with k = 0 (use the first cylinder and see if it helps in any record), then d [2] [2] will be equal to d [2-1] [2-1] +1 = d [1] [1] + 1 = 2

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