   # Travelling salesman problem is an example of

187 views
Dynamic Algorithm
Greedy Algorithm
Recursive Approach
Divide & Conquer posted Nov 26, 2017
Looking for an answer?  Promote on:
Similar Questions
+1 vote

While reading possible time complexity i found that time complexity O(log log n) exist for some algos,

Can any one explain an example which shows the calculation of the time complexity with O(log log n)

+1 vote

Given an array of denominations and array Count , find minimum number of coins required to form sum S.

for example:

``````  coins[]={1,2,3};
count[]={1,1,3};
``````

i.e we have 1 coin of Rs 1 , 1 coin of Rs 2 , 3 coins of Rs 3.

Now if we input S = 6 then output should be 2 with possible combination : 3+3 = 6

suppose we have an array of N natural numbers and asks him to solve the following queries:-
Query a:- modify the element present at index i to x.
Query b:- count the number of even numbers in range l to r inclusive.
Query c:- count the number of odd numbers in range l to r inclusive.

input:
First line of the input contains the number N. Next line contains N natural numbers.Next line contains an integer Q followed by Q queries.
a x y - modify the number at index x to y.
b x y - count the number of even numbers in range l to r inclusive.
c x y - count the number of odd numbers in range l to r inclusive.
I tried to solve using simple arrays but it isn't doing well for big constraints so I thought to use other DS with efficient algorithm so please explain appropriate algorithm.Thanks in advance.

+1 vote

``````  Profit Weight
1) 30    10
2) 50    5
3) 20    12
4) 70    40
5) 90    15
``````

The knapsack size is 50. Make the selection criteria based on : min weight, max profit and Ratio.

Standard Coin denomination problem is as follows

coin set = {1,2,5,10 ... } - each coin count is unlimited
find count of possible combinations of coins to create N Rs

This problem can either be done using backtracking or dynamic programming

Now My requirement added a factor where max count of each coin is given e.g.

{ (1, 10), (2, 5), (5, 4), (10, 100) } where (n,m) denotes m coins are of each n Rupees.

This can be done using backtracking by an addition check while inserting element to stack but this takes exponential time. Can somebody provides solution using dynamic programming ?