Write a C++ program called assignment.cpp. Your program should read the assignme
ID: 3872650 • Letter: W
Question
Write a C++ program called assignment.cpp. Your program should read the assignment costs of each person from a user and determine the best assignment. In the program, you can assume that the number of all jobs is less than 15.
Sample Program:
$ g++ -o assignment assignment.cpp
$ ./assignment
Number of jobs: 2
Enter assignment costs of 2 persons:
Person 1: 2 5
Person 2: 4 6
Permutation 1: <1, 2> => total cost: 8
Permutation 2: <2, 1> => total cost: 9
Solution: <1, 2> => total cost: 8
Explanation / Answer
#include <iostream>
#include <climits>
#include <cstdlib>
using namespace std;
int *ans;
int **costs;
//int count;
void permute(int a[],int l,int r,int count,int n,int lcost)
{
int tcost=0;
if(l==r)
{
/*for(int i=0;i<n;i++)
{
cout<<a[i]<<" ";
}*/
//cout<<endl;
count++;
cout<<"Person "<<count<<": <";
for(int i=0;i<n;i++)
{
cout<<a[i]+1;
if(i!=n-1)
{
cout<<", ";
}
tcost+=costs[i][a[i]];
}
cout<<"> => total cost:"<<tcost<<endl;
if(tcost<lcost)
{
lcost = tcost;
for(int i =0;i<n;i++)
{
ans[i] = a[i];
}
}
}
else
{
int temp;
for(int i=l;i<=r;i++)
{
temp = a[i];
a[i] = a[l];
a[l] = temp;
permute(a,l+1,r,count,n,lcost);
temp = a[i];
a[i] = a[l];
a[l] = temp;
}
}
}
int main()
{
int lcost;
lcost = INT_MAX;
int n;
//int count=0;
cout<<"Number of jobs: ";
cin>>n;
costs = (int **)malloc(sizeof(int*)*n);
cout<<"Enter assignment costs of "<<n<<" persons:"<<endl;
for(int i=0;i<n;i++)
{
costs[i] = (int *)malloc(sizeof(int)*n);
cout<<"Person "<<i+1<<": ";
for(int j=0;j<n;j++)
{
cin>>costs[i][j];
}
}
ans = (int *)malloc(sizeof(int)*n);
for(int i=0;i<n;i++)
{
ans[i] = i;
}
permute(ans,0,n-1,0,n,lcost);
int ans_cost=0;
cout<<"Solution: <";
for(int i=0;i<n;i++)
{
cout<<ans[i]+1;
if(i!=n-1)
{
cout<<", ";
}
ans_cost+=costs[i][ans[i]];
}
cout<<"> => total cost: "<<ans_cost<<endl;
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.