fork download
copy 
  1. #include <algorithm>
  2. #include <functional>
  3. #include <iostream>
  4. #include <stack>
  5. #include <string>
  6. #include <vector>
  7. #include <iterator>
  8.  
  9. using namespace std;
  10. using namespace std::placeholders;
  11.  
  12. #define IT(v) (v).begin(), (v).end()
  13.  
  14. template <class Iterator>
  15. void print_it(Iterator vbegin, Iterator vend) {
  16. 	if (vbegin == vend) return;
  17. 	cout << *vbegin;
  18. 	for (auto v = vbegin + 1; v!= vend; ++v) {
  19. 		cout << ", " <<  *v;
  20. 	}
  21. 	cout << endl;
  22. }
  23.  
  24. template <class Iterator1, class Iterator2, class F>
  25. auto zip_with(Iterator1 vbegin, Iterator1 vend, 
  26. 		Iterator2 wbegin, Iterator2 wend,
  27. 		F f) -> vector<decltype(f(*vbegin, *wbegin))> {
  28. 	vector<decltype(f(*vbegin, *wbegin))> r {};
  29. 	Iterator1 v = vbegin;
  30. 	Iterator2 w = wbegin;
  31. 	for (; v != vend && w != wend; ++v, ++w) {
  32. 		r.push_back(f(*v, *w));
  33. 	}
  34. 	return r;
  35. }
  36.  
  37. struct Process {
  38. 	string name;
  39. 	vector<int> allocation;
  40. 	vector<int> max;
  41. 	bool can_allocate(const vector<int>& available) const;
  42. 	vector<int> unallocate(const vector<int>& available) const;
  43. };
  44.  
  45. bool operator==(const Process& lhs, const Process& rhs) {
  46. 	return lhs.name == rhs.name 
  47. 		&& lhs.allocation == rhs.allocation
  48. 		&& lhs.max == rhs.max;
  49. }
  50.  
  51. struct DfsData {
  52. 	vector<int> available;
  53. 	vector<Process> processes;
  54. };
  55.  
  56. bool Process::can_allocate(const vector<int>& available) const {
  57. 	auto need = zip_with(IT(max), IT(allocation), minus<int>());
  58. 	auto test = zip_with(IT(need), IT(available), less_equal<int>());
  59. 	return all_of(IT(test), [](bool b) { return b; });
  60. }
  61.  
  62. vector<int> Process::unallocate(const vector<int>& available) const {
  63. 	return zip_with(IT(available), IT(allocation), plus<int>());
  64. }
  65.  
  66. vector<Process> solve_bankers(
  67. 		vector<int> available,
  68. 		vector<Process> processes) {
  69. 	stack<DfsData> s;
  70. 	s.push({
  71. 		.available = available,
  72. 		.processes = {}
  73. 	});
  74. 	while(!s.empty()) {
  75. 		DfsData d = s.top();
  76. 		s.pop();
  77. 		if (processes.size() == d.processes.size()) {
  78. 			return d.processes;
  79. 		}
  80. 		for (const auto&  p : processes) {
  81. 			if (d.processes.end() == std::find(IT(d.processes), p)
  82. 					&& p.can_allocate(d.available)) {
  83. 				vector<Process> ps (d.processes);
  84. 				ps.push_back(p);
  85. 				s.push({
  86. 					.available = p.unallocate(d.available),
  87. 					.processes = ps,
  88. 				});
  89. 			}
  90. 		}
  91. 	}
  92. 	return {};
  93. }
  94.  
  95. int main() {
  96. 	vector<int> available {3,3,2};
  97. 	vector<Process> processes {
  98. 		{.name = "P0", .allocation = {0,1,0}, .max = {7,5,3}},
  99. 		{.name = "P1", .allocation = {2,0,0}, .max = {3,2,2}},
  100. 		{.name = "P2", .allocation = {3,0,2}, .max = {9,0,2}},
  101. 		{.name = "P3", .allocation = {2,1,1}, .max = {2,2,2}},
  102. 		{.name = "P4", .allocation = {0,0,2}, .max = {4,3,3}},
  103. 	};
  104.  
  105. 	auto solution = solve_bankers(available, processes);
  106. 	vector<string> names {};
  107. 	for (auto& s : solution) {
  108. 		names.push_back(s.name);
  109. 	}
  110. 	print_it(IT(names));
  111.  
  112. 	return 0;
  113. }
Success #stdin #stdout 0s 4304KB
comments ()
stdin
copy 
Standard input is empty
stdout
copy 
P3, P4, P1, P2, P0
https://ideone.com/a83h9i
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!