银行家算法-安全序列全列出实现
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<string>
#include<queue>
#include<climits>
#include<map>
#include<stack>
#include<list>
#include<set>
#include<ctime>
#include<cstdlib>
#include<sstream>
#define file_in freopen("input.txt","r",stdin)
#define MAX 100005
#define INF 0x3f3f3f3f
#define HASH 100019
#define MAX_C 100
#define MAP_IT(type1,type2) map<type1,type2>::iterator
using namespace std;
#define ll long long
#define FF(x,y,i) for(int i=x;i<y;i++)
struct process {
int num;
vector<int>max;
vector<int>occupied;
vector<int>need;
};
vector<int>ava;
vector<process>processList;
bool test(vector<int>pmu) {
vector<process>tempPro = processList;
vector<int>tempava = ava;
for (int i = 0; i < pmu.size(); i++) {
int currentPro = pmu[i];
for (int i = 0; i < tempPro[currentPro].need.size(); i++) {
if (tempPro[currentPro].need[i] > tempava[i])
return 0;
}
for (int i = 0; i < tempPro[currentPro].occupied.size(); i++) {
tempava[i] += tempPro[currentPro].occupied[i];
}
}
return true;
}
int main() {
int numProcess, numRes;
cout << "Please input number of processes" << endl;
cin >> numProcess;
processList.resize(numProcess);
cout << "please input the number of resource types" << endl;
cin >> numRes;
for (int i = 0; i < numProcess; i++)
{
processList[i].max.resize(numRes);
processList[i].occupied.resize(numRes);
processList[i].need.resize(numRes);
}
ava.resize(numRes);
cout << "for each kind of resource, please input it's number of remaining instances" << endl;
for (int i = 0; i < numRes; i++)
cin >> ava[i];
cout << "for each process, input the occuied instance it owns by the order" << endl;
for (int i = 0; i < numProcess; i++) {
cout << "process" << i <<":"<< endl;
for (int j = 0; j < numRes; j++) {
cin >> processList[i].occupied[j];
}
}
cout << "for each process, input the maxium instance it needs" << endl;
for (int i = 0; i < numProcess; i++) {
cout << "process" << i << ":" << endl;
for (int j = 0; j < numRes; j++) {
cin >> processList[i].max[j];
processList[i].need[j] = processList[i].max[j] - processList[i].occupied[j];
}
}
vector<int>possiblePermu;
for (int i = 0; i < processList.size(); i++)possiblePermu.push_back(i);
while (next_permutation(possiblePermu.begin(), possiblePermu.end())) {
if (test(possiblePermu)) {
for (int i = 0; i < possiblePermu.size(); i++)
cout << possiblePermu[i] << " ";
cout << endl;
}
}
}