蓝莓 (SPOJ) - 超过动态规划时间限制

Question

我正在解决关于 spoj 的 problem。问题有一个简单的递归解决方案。

问题：给定一个大小为 n 的数字数组，select 一组数字使得 集合中没有两个元素是连续的和子集元素之和会尽可能接近k，但不要超过它。

我的递归方法

我使用了一种类似于背包的方法，在划分问题时，一个包含当前元素，另一个忽略它。

  function solve_recursively(n, current, k)
     if n < 0
        return current
     if n == 0
        if current + a[n] <= k
           return current + a[n]
        else
           return current
     if current + a[n] > k
        return recurse(n-1, current, k)
     else
        return max(recurse(n-1, current, k), recurse(n-2, current+a[n], k))

后来因为它本质上是指数级的，所以我使用 map（在 C++ 中）进行记忆以降低复杂性。

我的源代码：

struct k{
  int n; 
  int curr;
};

bool operator < (const struct k& lhs, const struct k& rhs){
  if(lhs.n != rhs.n)
    return lhs.n < rhs.n;
  return lhs.curr < rhs.curr;
};

int a[1001];
map<struct k,int> dp;

int recurse(int n, int k, int curr){
  if(n < 0)
    return curr;
  struct k key = {n, curr};
  if(n == 0)
    return curr + a[0] <= k ? curr + a[0] : curr;
  else if(dp.count(key))
    return dp[key];
  else if(curr + a[n] > k){
    dp[key] = recurse(n-1, k, curr);
    return dp[key];
  }
  else{
    dp[key] = max(recurse(n-1, k, curr), recurse(n-2, k, curr+a[n]));
    return dp[key];
  }
}

int main(){
  int t,n,k;
  scanint(t);
  while(t--){
    scanint(n);
    scanint(k);
    for(int i = 0; i<n; ++i)
      scanint(a[i]);
    dp.clear();
    printf("Scenario #%d: %d\n",j, recurse(n-1, k, 0));
  }
  return 0;
}

我检查了给定的测试用例。它清除了它们。但是我在提交时得到了错误的答案。

编辑： 早些时候我的输出格式是错误的，所以我得到了错误的答案。但是，现在它显示 超出时间限制 。我认为自下而上的方法会有所帮助，但我在制定一种方法时遇到了问题。我将其作为自下而上的背包来处理，但在精确表述方面存在一些困难。

Answer 1

据我了解，您几乎找到了解决方案。如果递归关系正确但效率太低，则只需将递归更改为迭代即可。显然，您已经有了代表状态及其各自值的数组 dp。基本上你应该能够用 n、k 和 curr 的三个嵌套循环来解决 fill dp，这将分别增加以确保 [=10= 中的每个值] 需要的已经计算好了。然后将对 recurse 的递归调用替换为对 dp.

的访问

蓝莓 (SPOJ) - 超过动态规划时间限制

Blueberries (SPOJ) - Dynamic Programming Time Limit Exceeded

c

c++

algorithm

knapsack-problem

dynamic-programming