动态规划 SPOJ 问题 SCUBADIV

Question

我正在尝试解决来自SPOJ的问题，这是一个动态规划问题，但是我很难想象递归步骤。我相信它类似于背包问题，但这里有两个约束条件：氧气和氮气。

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

- user866098

---

那么，你有什么问题？你尝试过什么？ - Mat

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循环必须从最大值向下到当前气缸的值，否则您将允许一个气缸被多次使用。

问题限制非常小，我认为这应该可以解决。

- IVlad

---

我不明白为什么循环必须向下进行。如果它向上增加，应该有相同的效果，对吗？ - user866098

@user866098 - 不，如果它在增加，那么如果你在计算某个 [i, j] 时使用了圆柱体 k，则也可以使用它来计算 [i-oxygen[k]，j-oxygen[k]]，这意味着你对 [i, j] 使用了两次，而 SPOJ 问题不允许这样做（尽管允许这样做的问题也是完全有效的）。 - IVlad

@User866098 - 尝试手动在小型测试中运行它。例如，如果您使用某个气缸x，其中 oxygen[x] = 2且 nitrogen[x] = 4来查找 dp [3,5]，那么如果您按升序遍历循环，还可以使用它来查找 dp [5,9] ，这是不希望的，因为这意味着您在 dp [5,9] 中使用了两次它。 - IVlad

初始值不应该是无穷大，而应该是0吗？因为：dp[5,9] = min(dp[5,9],dp[3,5]+weight[k])。如果dp[3,5]最初是无穷大，那么inf + weight[k]就会出错，对吗？ - user866098

假设maxTotalOxygen是所有氧气罐价值之和，通过加入一个含有大量氧氮的重型气罐，可以创建一个非常庞大的搜索空间。 看起来应该有一条更有效的路线，因为很多搜索空间不需要被探索（类似于三重嵌套的for循环）。 - Richard

Answer 2

@IVlad非常好的回答，谢谢:)

然而有一个陷阱:

以下内容应该被删除：

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

请使用这个代替：

并使用此内容：

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

前面的语句不是有效的基本情况，因为它允许气缸被使用两次。

如何实现呢？

最外层循环的不变量是在第n（k的迭代）次迭代中，我们尝试对于每个i,j计算出至少需要i个氧和j个氮来获得至少这些值的最小重量，使用的只有1到N个气缸（每个气缸只用一次）。

考虑以下测试用例：需要2个氧和2个氮，并且我们有2个气缸，一个有1 ox 1 ni 1 weight，另一个是2 ox 2 ni 50 weight

答案应该是50，因为我们不能使用第一个气缸两次。

我认为错误的基本情况将在我们开始循环之前填入d [1] [1] = 1。

然后循环从k = 0开始（使用第一个气缸并查看它是否对任何条目有帮助），那么d [2] [2]将等于d [2-1] [2-1] + 1 = d [1] [1] +1 = 2.

最终答案将是2个单位的重量，因为由于基本情况，第一个气缸被使用了两次，这是不正确的。

- MohamedEzz