Tugas3_5 No1

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

// Fungsi untuk menghitung biaya total dari sebuah penugasan.
int calculateCost(const vector<vector<int>>& assignments, const vector<vector<int>>& costs) {
int totalCost = 0;
for (int i = 0; i < assignments.size(); i++) {
int person = assignments[i][0];
int job = assignments[i][1];
totalCost += costs[person][job];
}
return totalCost;
}

// Fungsi untuk mencari penugasan dengan biaya minimum menggunakan metode exhaustive search.
void exhaustiveSearch(const vector<vector<int>>& costs) {
int n = costs.size();

// Membuat vektor indeks dari 0 hingga n-1.
vector<int> indices(n);
for (int i = 0; i < n; i++) {
    indices[i] = i;
}

// Mencari seluruh kemungkinan penugasan dengan biaya minimum.
int minCost = INT_MAX;
vector<vector<int>> minAssignments(n);
do {
    vector<vector<int>> assignments(n);
    for (int i = 0; i < n; i++) {
        assignments[i] = {i, indices[i]};
    }
    int cost = calculateCost(assignments, costs);
    if (cost < minCost) {
        minCost = cost;
        minAssignments = assignments;
    }
} while (next_permutation(indices.begin(), indices.end()));

// Mencetak penugasan dengan biaya minimum.
cout << "Penugasan dengan biaya minimum: " << minCost << endl;
for (int i = 0; i < minAssignments.size(); i++) {
    cout << "Orang " << minAssignments[i][0] << " ditugaskan ke pekerjaan " << minAssignments[i][1] << endl;
}

}

int main() {
int n = 4;
vector<vector<int>> costs = {{9, 2, 7, 8}, {6, 4, 3, 7}, {5, 8, 1, 4}, {7, 6, 9, 4}};

exhaustiveSearch(costs);

return 0;

}