c - 错误答案: Scuba diver SPOJ

Question

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

问题陈述:我们有N≤1000选择具有氧气容量、氮气容量和重量O[i]、N[i]和W[i]的气 jar 分别O≤21，N≤79，W≤800。我们需要足够的气瓶来分别补充氧气和氮气来完成潜水。找出完成潜水所需的最小气瓶总重量。

我已经实现了 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 个储 jar 轻松供应 0 个氧气和 0 个氮气。

此错误将导致您的代码错过每个最小解决方案，其中储 jar 完全满足氧气和氮气需求，没有剩余，因为所有这些决策序列都以dp结束[0][0][0] 将最后一个水箱添加到当前部分解后的子问题。要解决这个问题，您所需要做的就是颠倒最内层循环中前两个 if 测试的顺序。