Search found 3 matches

by mich
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.
by mich
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]...
by mich
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...

Go to advanced search