## Search found 3 matches

Mon Jun 05, 2006 10:11 pm
Forum: Volume 101 (10100-10199)
Topic: 10130 - SuperSale
Replies: 76
Views: 22640
Yes, I know it is a 0-1 knapsack problem, my function does just that, just that I am using recursion(with memoization) instead of DP.
Mon Jun 05, 2006 9:41 pm
Forum: Volume 101 (10100-10199)
Topic: 10130 - SuperSale
Replies: 76
Views: 22640

### 10130 - SuperSales

Hi, I am getting TLE on problem 10130. Here is the code for my function calculating the max each person can buy (works fine on the sample test cases). int best(int w, int i1) { int t = 0; if(cache[w][i1] != -1) return cache[w][i1]; for(int i = i1; i < 1000; i++) { if(o1[i] == -1) break; if( (w-o2[i]...
Sun Jun 04, 2006 9:18 pm
Forum: Algorithms
Topic: LCS
Replies: 1
Views: 1101

### LCS

Hello, Can anybody help me find the flaw in my LCS algorithm: int LCS(int a, int b) { if(a >= (int)s1.size() || b >= (int)s2.size() ) return 0; if(cache[a][b] != -1) return cache[a][b]; if(s1[a] == s2[b]) { return 1+LCS(a+1,b+1); } int answer = max(LCS(a+1, b), LCS(a, b+1)); cache[a][b]=answer; retu...