c - 动态规划SPOJ问题SCUBADIV

Question

我正试图从 SPOJ 解决这个问题，这是一个动态规划问题，但我在可视化递归步骤时遇到了问题。我相信它类似于背包，但这里有氧气和氮气两个约束条件。

这是链接:http://www.spoj.pl/problems/SCUBADIV/

Answer 1

我认为这应该可行:

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.

请注意，for 循环必须从最大值向下到当前柱面的值，否则您将允许一个柱面被多次使用。

问题约束非常小，我认为这应该可行。