leo
BAN USERhere is my solution. I think the complexity is bad.
If someone has better implementation.
Please give out. I will very appreciate.
int KnapSack(int capacity, int v[], int w[], int index, int num) {
if(capacity<0 || index>=num)
return 10000;
if(capacity == 0)
return 0;
int a = v[index] + KnapSack(capacity-w[index], v, w, index, num);
int b = KnapSack(capacity, v, w, index+1, num);
return min(a, b);
}
int SmallestImpossible(int v[], int w[], int capacity, int num) {
int smallest = 10000, c = 0;
for(int i=0; i<num; i++) {
int tmp = KnapSack(capacity+w[i], v, w, 0, num);
if(tmp < smallest) {
smallest = tmp;
c = capacity+w[i];
}
//cout << capacity+w[i] << " " << tmp << endl;
}
return smallest;
}
I think it is a classic problem in career cup.
- leo February 16, 2013The solution is: (assumption is we have the parent pointer)
1. keep move up both nodes by using parent pointer, and keep 2 counters.
after both of them reach the root. Then we have the two counters that
stores the steps which the node need to move to root.
2. By this we can get the difference between two counters. then move up the
larger-counter node only with the different steps. Finally, move both nodes
step by step, when they meet, that is the common ancestor.
Any problem with this method? or the time complexity is bad?