错误答案：Scuba潜水员SPOJ

Question

我正在SPOJ上尝试this problem。它基本上是0/1背包。

问题陈述：我们给N≤1000分别具有氧气容量，氮气容量和重量O [i]，N [i]和W [i] O≤21，N≤79，W≤800。我们需要足够的油箱分别为t氧气和氮气燃料以完成潜水。找到所需的最小油箱总重量以完成潜水。

我已经实现了3D动态编程解决方案。但是我得到了错误的答案。请帮助。

源代码：

int dp[1002][23][81];   // to store subproblems
int ox[1002],nt[1002],wt[1002]; // ox: oxygen; nt: nitrogen; wt = weight of cylinder

void solve(int n, int oxy, int nit){ // n: no. of cylinders, oxy: oxygen required; nit: nitrogen required
  for(int i = 0; i <=n; ++i)
    for(int j = 0; j <= oxy; ++j)
      for(int k = 0; k <= nit; ++k){
        if(i == 0)
          dp[i][j][k] = INF;
        else if(j == 0 && k == 0)
          dp[i][j][k] = 0;
        else
          dp[i][j][k] = min(dp[i-1][j][k], dp[i-1][max(j-ox[i], 0)][max(k-nt[i], 0)] + wt[i]);
      }
  printf("%d\n", dp[n][oxy][nit]);
}

请帮助。 Complete Source Code

Answer 1

问题是，您要为使用0个储罐的所有情况分配无限的重量（成本），包括错误地使用oxy = nit = 0的情况。在这种情况下（即dp[0][0][0]），分配的重量应为0，因为您可以使用0个储罐轻松地提供0氧气和0氮气。

此错误将导致您的代码丢失每个最小的解决方案，其中的储罐精确

满足氧气和氮气需求，而没有剩余，因为所有这些决策序列都在最后一个储罐之后的dp[0][0][0]子问题处结束被添加到当前的部分解决方案中。要解决此问题，您需要做的就是颠倒最内层循环中前两个if测试的顺序。

Answer 2

氧气或氮的需求量小于零时，将其替换为零。请参阅我的代码https://github.com/sahazeer123/SPOJ/blob/master/Scubadiver.cpp