top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

Travelling salesman problem is an example of

0 votes
1,223 views
ADynamic Algorithm
BGreedy Algorithm
CRecursive Approach
DDivide & Conquer

Correct Option: 2  

Explanation:
Travelling salesman is an example of greedy algorithm. Greedy algorithms tries to find localized optimum solution which may eventually land in globally optimized solutions.
posted Nov 26, 2017 by anonymous

Looking for an answer?  Promote on:
Facebook Share Button Twitter Share Button LinkedIn Share Button

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

+2 votes

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

Please help me to solve the Knapsack problem using greedy algorithms.

  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.

+3 votes

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 ?

thanks in advance..

...