Черника (SPOJ) — превышено ограничение по времени динамического программирования

Я решал проблема на спой. Задача имеет простое рекурсивное решение.

Проблема: дан массив чисел размера N, выберите набор чисел так, чтобы нет двух элементов в наборе подряд а также сумма элементов подмножества будет как можно ближе к, но не должен превышать его.

Мой рекурсивный подход

Я использовал подход, аналогичный ранцу, при разделении задачи так, что один включает текущий элемент, а другой игнорирует его.

  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;
}

Я проверил на данные тестовые случаи. Это очистило их. Но я получаю неправильный ответ при представлении.

РЕДАКТИРОВАТЬ: Ранее мой формат вывода был неправильным, поэтому я получил неправильный ответ. Но теперь его показ Превышен лимит времени. Я думаю, что подход «снизу вверх» был бы полезен, но у меня возникла проблема при его формулировании. Я подхожу к нему как к рюкзаку снизу вверх, но у меня есть некоторые трудности в точной формулировке.