Suppose we have a set of N agents and a set of N tasks.Each agent can only perform exactly one task and there is a cost associated with each assignment. We would like to find out an assignment which results in the least total cost. Your task is to write a c++ program to implement the branch and bound algorithm to solve this assignment problem.

Your program should read input data from a input file named "infile.txt". The format for the input file is as follows: First line is an integer N representing the number of agents and the number of jobs. In the next N lines, each line j (1 ≤ j ≤ N) consists of N integers representing the cost of assigning agent j to each of the N tasks.

Figure 1 gives you an example of the input format. For example, the cost of assigning agent 1 to task 1, 2, 3 and 4 are 11, 12, 18 and 40 respectively.

4 11 12 18 40 14 15 13 22 11 17 19 23 17 14 20 28

Figure 1

Total cost: 61 (1,1) (2,3) (3,4)  (4,2)

Figure 2

Output, to standard output, will consist of:

• Total cost of the assignment
• In the next N lines, each line j (1 ≤ j ≤ N) shows the task assignment for agent j in the format "(j,k)", which means agent j is assigned to task k.

Figure 2 gives you an example of the output screen for the input file in Figure 1.

Posted Date: 2/25/2013 6:56:11 AM | Location : United States

Ask an Expert

Related Discussions:- Branch and bound algorithm, Assignment Help, Ask Question on Branch and bound algorithm, Get Answer, Expert's Help, Branch and bound algorithm Discussions

Write discussion on Branch and bound algorithm
Your posts are moderated

Write your message here..

Related Questions

Operations on b-trees, Operations on B-Trees Given are various operatio... Operations on B-Trees Given are various operations which can be performed on B-Trees: Search Create Insert B-Tree does effort to minimize disk access and t

State algorithm to insert node p at the end of a linked list, Algo rithm t... Algo rithm to Insert a Node p at the End of a Linked List is explained below Step1:   [check for space] If new1= NULL output "OVERFLOW" And exit Step2:   [Allocate fr

Find longest repeat prefix of string - linear time algorithm, 1. A string s... 1. A string s is said to be periodic with a period α, if s is α k for some k > 2. (Note that α k is the string formed by concatenating k times.) A DNA sequence s is called a tand

Explain merge sort, Merge sort: Merge sort is a sorting algorithm that ... Merge sort: Merge sort is a sorting algorithm that uses the idea of split and conquers. This algorithm splits the array into two halves, sorts them separately and then merges t

Creation of Heap, Q. Create a heap with the given list of keys: ... Q. Create a heap with the given list of keys: 8, 20, 9, 4, 15, 10, 7, 22, 3, 12                                                  Ans: Creation

Find error for curious number, #include #include int sumFact(int numb);... #include #include int sumFact(int numb); int calculateFactorial(int digit); main() { int numb, sumfact; do{ printf ("Enter a number 1 to 9999\n"); scanf("%

Algorithms, characteristics of a good algorithm characteristics of a good algorithm

How to measure the algorithm efficiency, How to measure the algorithm's eff... How to measure the algorithm's efficiency? It is logical to examine the algorithm's efficiency as a function of some parameter n showing the algorithm's input size. Instance

Array vs. ordinary variable, Q. Describe what do you understand by the term... Q. Describe what do you understand by the term array? How does an array vary from an ordinary variable? How are the arrays represented in the specific memory?

Sparse matrix, How sparse matrix stored in the memory of a computer? How sparse matrix stored in the memory of a computer?