我正在尝试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
最佳答案
问题在于,您为所有使用 0 个水箱的情况分配了无限的权重(成本)——包括错误的 oxy = nit = 0 的情况。在这种情况下(即 dp[0][0][0]
),分配的权重应为 0,因为您可以使用 0 个储 jar 轻松供应 0 个氧气和 0 个氮气。
此错误将导致您的代码错过每个最小解决方案,其中储 jar 完全满足氧气和氮气需求,没有剩余,因为所有这些决策序列都以dp结束[0][0][0]
将最后一个水箱添加到当前部分解后的子问题。要解决这个问题,您所需要做的就是颠倒最内层循环中前两个 if
测试的顺序。
关于c - 错误答案: Scuba diver SPOJ,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/28165227/