akki
BAN USERThis is a simplified form of box stacking problem. An optimized solution can be given using Dynamic Programming.
1) Sort boxes on basis of base area (higher to lower) .
Now we define h(j) = max height with which box j ends up on the top.
h(j) = max(h(i)) + height of jth tower, such that li > lj and wi > wj for all i <j.
By formulating this recursion we will get the answer.
In BFS algo we maintain parent info for every node except the root(one from which BFS call is being started). Suppose v is in adjancey of u then we maintain a parent[v] = u, sort of info. So to generate the path you can write a recursive function which uses this info and print the path.
void printPath(node v, node s){
if(v == s){
printf("%s",s);
return;
}
printPath(parent(v),s);
printf("%s",parent(v));
}
Even trie takes time proportional to length of word for searching then how can it be more efficient here ?
- akki August 26, 2012And we would have to spend resources in maintaining and creating trie.