求助 有关于21题 01背包问题的递归法实现

[para3in]

在pc上能跑并且秒出答案（对于ice上的两组测试集运行的答案都是正确的），在ice上显示超时。我看了一下，递归函数（knapsack）的出口是n=0或c=0，在n>0，c>0的时候，经过有限次变换一定能到达出口，所以应该不存在死循环的情况吧……？反正ice和我肯定有一个拉了，还恳请好心的大佬指教啊TAT （下面是代码）

include

using namespace std; int getmax(int a, int b) { if (a >= b) return a; else return b; } int knapsack(int n, int s[], int v[], int C) { if (n == 0 or C == 0) return 0; else { if (s[n - 1] > C) return knapsack(n - 1, s, v, C); else return getmax(knapsack(n - 1, s, v, C), knapsack(n - 1, s, v, C-s[n-1])+v[n-1]);

}

}

int main() { int n, C, s[2000], v[2000]; cin >> C >> n;

for (int i = 0; i < n; i++)
    cin >> s[i] >> v[i];

cout << knapsack(n, s, v, C) << endl;
return 0;

}

[Liangzheng-ZL]

对于0-1背包问题，建议考虑动态规划、贪心算法等，原始递归时间复杂度太大。