Travelling salesman problem is an example of

1,250 views

ADynamic Algorithm

BGreedy Algorithm

CRecursive Approach

DDivide & Conquer

posted Nov 26, 2017 by anonymous

Looking for an answer? Promote on:

Similar Questions

+1 vote

Give an example of Algo/Program whose time complexity is O(log log n) ?

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

Coin Change Problem: minimum number of coins required to form sum S.

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

How to solve this problem using c++ with operations in log complexities for both update and count?

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

Knapsack problem with size 50?

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

Coin Denomination Problem Solution in polynomial time

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..

Travelling salesman problem is an example of

Your comment on this post: