银行家算法代码

/*银行家算法  Banker Algorithm*/
/*算法思路：dfs（深度优先遍历）*/
import java.util.*;
public class Main{  
  static class Process{ // 每个进程的情况
    public Resources max;
    public Resources allocation;
    public Resources need;
    public Process() {
      // TODO Auto-generated constructor stub
    }
    public Process(Resources max, Resources allocation, Resources need)
    {
      this.max = max;
      this.allocation = allocation;
      this.need = need;
    }
  }
  static class Resources  // 这里以三个资源为例子
  {
    int A, B, C;
    public Resources(int A, int B, int C) {
      this.A = A;
      this.B = B;
      this.C = C;
      //System.out.println("RE" + this.A + " " + this.B + " " + this.C);
    }
    void showAll()  // 查看当前的资源的占比情况 调试用的
    {
      System.out.println("A:" + A + " " + "B:" + B + " " + "C:" + C);
    }
  }
  static List<Process> pset = new ArrayList<Process>();   // 存放每个进程的情况
  static List<Integer> v = new ArrayList<Integer>();  // 存放最后的安全序列的
  static int N = 110;   // 资源的最大个数的限制
  static boolean [] st = new boolean[N];   // dfs的辅助数组
  static int n;
  static Resources available;    // 把可用的资源定义为全局数组 方便修改
  static int cnt = 0;   // 存放最后的结果数
  public static void main(String[] args) { 
    Scanner in = new Scanner(System.in);
    System.out.print("输入进程数：");
    n = in.nextInt();  // 进程的数量
    int a, b, c;
    int i = 0;
    int t = n;
    while(t -- > 0)
    {     
      System.out.println("输入进程P" + i + "的Max:");
      System.out.print("A:");
      a = in.nextInt();
      System.out.print("B:");
      b = in.nextInt();
      System.out.print("C:");
      c = in.nextInt();
      i ++;
      Resources max = new Resources(a, b, c);
      System.out.println("输入Allocation:");
      System.out.print("A:");
      a = in.nextInt();
      System.out.print("B:");
      b = in.nextInt();
      System.out.print("C:");
      c = in.nextInt();     
      Resources allocation = new Resources(a, b, c);
      pset.add(new Process(max, allocation, Sub(max, allocation)));
    }
    System.out.println("输入Available:");
    System.out.print("A:");
    a = in.nextInt();
    System.out.print("B:");
    b = in.nextInt();
    System.out.print("C:");
    c = in.nextInt();
    available = new Resources(a, b, c);
    if (n == 0) return;   
    dfs(0);
    if (cnt == 0) System.out.println("没有安全序列");
    System.out.println("安全序列的数量：" + cnt);
  }
  static Resources Sub(Resources r1, Resources r2)  // 计算两个资源集合相减的结果
  {
    Resources r = new Resources(r1.A - r2.A, r1.B - r2.B, r1.C - r2.C);
//    System.out.println("Sub");
//    r.showAll();
    return r;
  }
  static Resources Add(Resources r1, Resources r2)  // 两个资源集合相加
  {
    Resources r = new Resources(r1.A + r2.A, r1.B + r2.B, r1.C + r2.C);
//    System.out.println("Add:");
//    r.showAll();
    return r;
  }
  static boolean CP(Resources r1, Resources r2) // 对两个资源集合进行比较 r1 <= r2返回true
  {
    boolean flag = false;
    if (r1.A <= r2.A && r1.B <= r2.B && r1.C <= r2.C) flag = true;
//    if (flag == false)
//    {
//      System.out.println("r1 ");
//      r1.showAll();
//      System.out.println("r2 ");
//      r2.showAll();
//    }
    return flag;
  }
  // 深度优先遍历的模板
  static void dfs(int u)
  {
    if (u == n)
    {
      cnt ++;   
      for (Integer it : v)   // 打印结果
      {
        System.out.print("P" + it + " ");
      }
      System.out.println();
      return;
    }
    for (int i = 0; i < n; ++ i)
    {
      Resources t1 = pset.get(i).need;
      Resources t2 = pset.get(i).allocation;
      if (!st[i] && CP(t1, available)) // 如果当前的这个进程的need小于available而且没有被访问过
      {
        st[i] = true;
        available = Add(t2, available);
        v.add(i);
        dfs(u + 1);
        available = Sub(available, t2);
        st[i] = false;
        v.remove(v.size() - 1);
      }
    }
  }
}

输入进程数：5
输入进程P0的Max:
A:7
B:5
C:3
输入Allocation:
A:0
B:1
C:0
输入进程P1的Max:
A:3
B:2
C:2
输入Allocation:
A:2
B:0
C:0
输入进程P2的Max:
A:9
B:0
C:2
输入Allocation:
A:3
B:0
C:2
输入进程P3的Max:
A:2
B:2
C:2
输入Allocation:
A:2
B:1
C:1
输入进程P4的Max:
A:4
B:3
C:3
输入Allocation:
A:0
B:0
C:2
输入Available:
A:3
B:3
C:2
P1 P3 P0 P2 P4 
P1 P3 P0 P4 P2 
P1 P3 P2 P0 P4 
P1 P3 P2 P4 P0 
P1 P3 P4 P0 P2 
P1 P3 P4 P2 P0 
P1 P4 P3 P0 P2 
P1 P4 P3 P2 P0 
P3 P1 P0 P2 P4 
P3 P1 P0 P4 P2 
P3 P1 P2 P0 P4 
P3 P1 P2 P4 P0 
P3 P1 P4 P0 P2 
P3 P1 P4 P2 P0 
P3 P4 P1 P0 P2 
P3 P4 P1 P2 P0 
安全序列的数量：16