Need help in designing efficient backtracking algorithm for the coin
changing problem. where a1, a2, an are the set of distinct coins
types, where each ai is an integer. and each type is unlimited
quantity.
the problem to make up the exact amount C using minimum total number
of coins. use
this is dynamic programming problem. try to use dynamic programming...
On Sat, Apr 10, 2010 at 9:12 AM, «« ÄÑÜJ »» anujlove...@gmail.com wrote:
Need help in designing efficient backtracking algorithm for the coin
changing problem. where a1, a2, an are the set of distinct coins
types, where
y u need backtracking
i think it can be done with DP
On Sat, Apr 10, 2010 at 9:12 AM, «« ÄÑÜJ »» anujlove...@gmail.com wrote:
Need help in designing efficient backtracking algorithm for the coin
changing problem. where a1, a2, an are the set of distinct coins
types, where each ai is an
What do u mean by y u need backtracking
DP needs backtracking to reconstruct the solution.
-Rohit
On Sat, Apr 10, 2010 at 3:27 PM, Ashish Mishra amishra@gmail.comwrote:
y u need backtracking
i think it can be done with DP
On Sat, Apr 10, 2010 at 9:12 AM, «« ÄÑÜJ »»
i have an problem on SPOJ to find all the prime less than 10^8
https://www.spoj.pl/problems/TDPRIMES/
i am using sieve of erastosthenes algorithm to find primes
my code is taking in my machine around 10.9 to 11.2 seconds
and time limit is 10 second how i can change my code or any diff logic..???
here is simple way to do it..:
A[1000] //1000 is maximum formadable sum can be provided..
S is set of coins that you have,K is the sum to be formed
initialize the array A by larege value
for(x in S):
A[x]=1
for 0i1000
for 0j1000
if(i+j1000 A[i]+A[j]A[i+j] )
Hi,
The book on data structures by Langsam and Tanenbaum gives an alternate
representation of trees as :
struct treenode {
int data;
struct treenode * son;
struct treenode * sibling;
};
Such type of nodes can be used to make trees in which each node can have any
It's equivalent to (x1-1)+(x2-1)+. . .+(xk-1)=n-k (You need n=k)
yi = xi - 1, so for every 1=i=k, we have that yi is non-negative.
Now think about it as having (n-1) objects in a row, and you need to choose
k-1 which will be black and the other n-k will be white so, the number of
solutions is
A binary search tree, nodes are ordered. So if you go to the left
subtree the data in all of the nodes is less than the data in current
node. Going to right subtree all the data will be greater than the
data in current node.
In short we need to define an order in that tree (how is the data
Your statement about the complexity of searching a binary search tree
applies only if the tree is balanced. In a degenerate tree, e.g.,
where each node has only one son, so that the tree is essentialy a
linked list, the complexity of searching is O(n).
Dave
On Apr 10, 10:56 am, Himanshu Aggarwal
why don't you remove all even numbers from consideration and add 2
explicitly. I think that would help.
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14
On Sun,
Construct a binary tree from the data (maintain the size of subtree under
each node).
Do rotations till the left subtree does not have size k. Rotation is a
constant time operation.
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science
hmm... that can always be done !
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14
On Wed, Mar 24, 2010 at 6:24 PM, Dave dave_and_da...@juno.com wrote:
Please
I realised now that it can be done easily as :
we can find the kth largest element in O(n) using Linear general selection
algorithm - Median of Medians algorithm
Well , can we do better than O(n log n ) in creating a BST from an array of
size n ?
14 matches
Mail list logo
