user866098 - 1 year ago 124
C Question

# Dynamic programming SPOJ problem SCUBADIV

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.

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.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download