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/
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.
@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 infinity everywhere else
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
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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With