错误答案：潜水员 SPOJ

Question

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

问题陈述：给定N≤1000选择氧气容量、氮气容量和重量O[i]、N[i ],和W[i]分别O≤21,N≤79,W≤800。我们需要足够的气瓶来分别为 吨氧气和氮气 提供燃料以完成潜水。找到完成潜水所需的气瓶总重量的最小值。

我已经实现了 3-D 动态规划解决方案。但我得到了错误的答案。请帮忙。

源代码：

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 个氮气。

此错误将导致您的代码错过每一个最小的解决方案，在这些解决方案中，罐正好满足氧气和氮气的需求，剩余 none，因为所有这些在将最后一个罐添加到当前部分解决方案后，决策序列在 dp[0][0][0] 子问题处结束。要修复它，您需要做的就是颠倒最内层循环中前两个 if 测试的顺序。

错误答案：潜水员 SPOJ

Wrong Answer : Scuba diver SPOJ

c

algorithm

knapsack-problem

dynamic-programming