class080 状压dp-上【算法】

package class080;
// 我能赢吗
// 给定两个整数n和m
// 两个玩家可以轮流从公共整数池中抽取从1到n的整数（不放回）
// 抽取的整数会累加起来（两个玩家都算）
// 谁在自己的回合让累加和 >= m，谁获胜
// 若先出手的玩家能稳赢则返回true，否则返回false
// 假设两位玩家游戏时都绝顶聪明，可以全盘为自己打算
// 测试链接 : https://leetcode.cn/problems/can-i-win/
public class Code01_CanIWin {
  public static boolean canIWin(int n, int m) {
    if (m == 0) {
      // 来自题目规定
      return true;
    }
    if (n * (n + 1) / 2 < m) {
      // 如果1~n数字全加起来
      // 累加和和是n * (n+1) / 2，都小于m
      // 那么不会有赢家，也就意味着先手不会获胜
      return false;
    }
    // dp[status] == 0 代表没算过
    // dp[status] == 1 算过，答案是true
    // dp[status] == -1 算过，答案是false
    int[] dp = new int[1 << (n + 1)];
    return f(n, (1 << (n + 1)) - 1, m, dp);
  }
  // 如果1~7范围的数字都能选，那么status的状态为：
  // 1 1 1 1 1 1 1 1
  // 7 6 5 4 3 2 1 0
  // 0位弃而不用
  // 如果1~7范围的数字，4、2已经选了不能再选，那么status的状态为：
  // 1 1 1 0 1 0 1 1
  // 7 6 5 4 3 2 1 0
  // 0位弃而不用
  // f的含义 :
  // 数字范围1~n，当前的先手，面对status给定的数字状态
  // 在累加和还剩rest的情况下
  // 返回当前的先手能不能赢，能赢返回true，不能赢返回false
  public static boolean f(int n, int status, int rest, int[] dp) {
    if (rest <= 0) {
      return false;
    }
    if (dp[status] != 0) {
      return dp[status] == 1;
    }
    // rest > 0
    boolean ans = false;
    for (int i = 1; i <= n; i++) {
      // 考察所有数字，但是不能选择之前选了的数字
      if ((status & (1 << i)) != 0 && !f(n, (status ^ (1 << i)), rest - i, dp)) {
        ans = true;
        break;
      }
    }
    dp[status] = ans ? 1 : -1;
    return ans;
  }
}

f(int status, int cur, int rest)
对于每一个没使用的火柴，(status&(1<<i))!=0
cur+nums[i]<=limit，并且不超过边长限制
if(cur+nums[i]==0)
  f(status^(1<<i),0,rest-1)
else
  f(status^(1<<i),cur+nums[i],rest)

package class080;
// 火柴拼正方形
// 你将得到一个整数数组 matchsticks
// 其中 matchsticks[i] 是第 i 个火柴棒的长度
// 你要用 所有的火柴棍 拼成一个正方形
// 你 不能折断 任何一根火柴棒，但你可以把它们连在一起，而且每根火柴棒必须 使用一次
// 如果你能拼出正方形，则返回 true ，否则返回 false
// 测试链接 : https://leetcode.cn/problems/matchsticks-to-square/
public class Code02_MatchsticksToSquare {
  public static boolean makesquare(int[] nums) {
    int sum = 0;
    for (int num : nums) {
      sum += num;
    }
    if (sum % 4 != 0) {
      return false;
    }
    int n = nums.length;
    int[] dp = new int[1 << n];
    return f(nums, sum / 4, (1 << n) - 1, 0, 4, dp);
  }
  // limit : 每条边规定的长度
  // status : 表示哪些数字还可以选
  // cur : 当前要解决的这条边已经形成的长度
  // rest : 一共还有几条边没有解决
  // 返回 : 能否用光所有火柴去解决剩下的所有边
  // 因为调用子过程之前，一定保证每条边累加起来都不超过limit
  // 所以status是决定cur和rest的，关键可变参数只有status
  public static boolean f(int[] nums, int limit, int status, int cur, int rest, int[] dp) {
    if (rest == 0) {
      return status == 0;
    }
    if (dp[status] != 0) {
      return dp[status] == 1;
    }
    boolean ans = false;
    for (int i = 0; i < nums.length; i++) {
      // 考察每一根火柴，只能使用状态为1的火柴
      if ((status & (1 << i)) != 0 && cur + nums[i] <= limit) {
        if (cur + nums[i] == limit) {
          ans = f(nums, limit, status ^ (1 << i), 0, rest - 1, dp);
        } else {
          ans = f(nums, limit, status ^ (1 << i), cur + nums[i], rest, dp);
        }
        if (ans) {
          break;
        }
      }
    }
    dp[status] = ans ? 1 : -1;
    return ans;
  }
}

package class080;
import java.util.Arrays;
// 划分为k个相等的子集
// 给定一个整数数组  nums 和一个正整数 k，
// 找出是否有可能把这个数组分成 k 个非空子集，其总和都相等。
// 测试链接 : https://leetcode.cn/problems/partition-to-k-equal-sum-subsets/
public class Code03_PartitionToKEqualSumSubsets {
  // 状压dp的解法
  // 这是最正式的解
  public static boolean canPartitionKSubsets1(int[] nums, int k) {
    int sum = 0;
    for (int num : nums) {
      sum += num;
    }
    if (sum % k != 0) {
      return false;
    }
    int n = nums.length;
    int[] dp = new int[1 << n];
    return f1(nums, sum / k, (1 << n) - 1, 0, k, dp);
  }
  // 就是题目2的递归函数
  public static boolean f1(int[] nums, int limit, int status, int cur, int rest, int[] dp) {
    if (rest == 0) {
      return status == 0;
    }
    if (dp[status] != 0) {
      return dp[status] == 1;
    }
    boolean ans = false;
    for (int i = 0; i < nums.length; i++) {
      if ((status & (1 << i)) != 0 && cur + nums[i] <= limit) {
        if (cur + nums[i] == limit) {
          ans = f1(nums, limit, status ^ (1 << i), 0, rest - 1, dp);
        } else {
          ans = f1(nums, limit, status ^ (1 << i), cur + nums[i], rest, dp);
        }
        if (ans) {
          break;
        }
      }
    }
    dp[status] = ans ? 1 : -1;
    return ans;
  }
  // 纯暴力的递归（不做任何动态规划），利用良好的剪枝策略，可以做到非常好的效率
  // 但这并不是正式的解，如果数据设计的很苛刻，是通过不了的
  public static boolean canPartitionKSubsets2(int[] nums, int k) {
    int sum = 0;
    for (int num : nums) {
      sum += num;
    }
    if (sum % k != 0) {
      return false;
    }
    int n = nums.length;
    Arrays.sort(nums);
    return f2(new int[k], sum / k, nums, n - 1);
  }
  // group里面是各个集合已经有的累加和
  // 随着递归的展开，group里的累加和会变化
  // 所以这是一个带路径的递归，而且路径信息比较复杂(group数组)
  // 无法改成动态规划，但是利用剪枝策略可以通过
  // group[0....index]这些数字，填入每个集合，一定要都使用
  // 每个集合的累加和一定都要是target，返回能不能做到
  public static boolean f2(int[] group, int target, int[] nums, int index) {
    if (index < 0) {
      return true;
    }
    int num = nums[index];
    int len = group.length;
    for (int i = 0; i < len; i++) {
      if (group[i] + num <= target) {
        // 当前数字num放进i号集合
        group[i] += num;
        if (f2(group, target, nums, index - 1)) {
          return true;
        }
        // 递归完成后将路径还原
        group[i] -= num;
        while (i + 1 < group.length && group[i] == group[i + 1]) {
          i++;
        }
      }
    }
    return false;
  }
}

package class080;
// 售货员的难题 - TSP问题
// 某乡有n个村庄(1<=n<=20)，有一个售货员，他要到各个村庄去售货
// 各村庄之间的路程s(1<=s<=1000)是已知的
// 且A村到B村的路程，与B到A的路大多不同(有向带权图)
// 为了提高效率，他从商店出发到每个村庄一次，然后返回商店所在的村，
// 假设商店所在的村庄为1
// 他不知道选择什么样的路线才能使所走的路程最短
// 请你帮他选择一条最短的路
// 测试链接 : https://www.luogu.com.cn/problem/P1171
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下的code，提交时请把类名改成"Main"，可以直接通过
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
// 正常来说把MAXN改成20能通过，实现是正确的
// 问题是卡空间，而且c++的实现不卡空间，就卡java的实现
// 但如果把MAXN改成19，会有一个测试用例通过不了
// 那就差这么一点空间...看不起java是吗？
// 好，你歧视java实现，那就别怪我了
// 完全能通过的版本看Code04_TSP2的实现
public class Code04_TSP1 {
  public static int MAXN = 19;
  public static int[][] graph = new int[MAXN][MAXN];
  public static int[][] dp = new int[1 << MAXN][MAXN];
  public static int n;
  public static void build() {
    for (int s = 0; s < (1 << n); s++) {
      for (int i = 0; i < n; i++) {
        dp[s][i] = -1;
      }
    }
  }
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StreamTokenizer in = new StreamTokenizer(br);
    PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
    while (in.nextToken() != StreamTokenizer.TT_EOF) {
      n = (int) in.nval;
      build();
      for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
          in.nextToken();
          graph[i][j] = (int) in.nval;
        }
      }
      out.println(compute());
    }
    out.flush();
    out.close();
    br.close();
  }
  public static int compute() {
    return f(1, 0);
  }
  // s : 村里走没走过的状态，1走过了不要再走了，0可以走
  // i : 目前在哪个村
  public static int f(int s, int i) {
    if (s == (1 << n) - 1) {
      // n : 000011111
      return graph[i][0];
    }
    if (dp[s][i] != -1) {
      return dp[s][i];
    }
    int ans = Integer.MAX_VALUE;
    for (int j = 0; j < n; j++) {
      // 0...n-1这些村，都看看是不是下一个落脚点
      if ((s & (1 << j)) == 0) {
        ans = Math.min(ans, graph[i][j] + f(s | (1 << j), j));
      }
    }
    dp[s][i] = ans;
    return ans;
  }
}

package class080;
// 售货员的难题 - TSP问题
// 某乡有n个村庄(1<=n<=20)，有一个售货员，他要到各个村庄去售货
// 各村庄之间的路程s(1<=s<=1000)是已知的
// 且A村到B村的路程，与B到A的路大多不同(有向带权图)
// 为了提高效率，他从商店出发到每个村庄一次，然后返回商店所在的村，
// 假设商店所在的村庄为1
// 他不知道选择什么样的路线才能使所走的路程最短
// 请你帮他选择一条最短的路
// 测试链接 : https://www.luogu.com.cn/problem/P1171
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下的code，提交时请把类名改成"Main"，可以直接通过
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
// 卡空间是吧？绕一下！
public class Code04_TSP2 {
  public static int MAXN = 19;
  public static int[] start = new int[MAXN];
  public static int[] back = new int[MAXN];
  // 这个图中，其实是不算起始村的，其他村庄彼此到达的路径长度
  public static int[][] graph = new int[MAXN][MAXN];
  // 不算起始村庄的
  public static int[][] dp = new int[1 << MAXN][MAXN];
  public static int n;
  public static void build() {
    for (int s = 0; s < (1 << n); s++) {
      for (int i = 0; i < n; i++) {
        dp[s][i] = -1;
      }
    }
  }
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StreamTokenizer in = new StreamTokenizer(br);
    PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
    while (in.nextToken() != StreamTokenizer.TT_EOF) {
      n = (int) in.nval - 1;
      build();
      in.nextToken();
      for (int i = 0; i < n; i++) {
        in.nextToken();
        start[i] = (int) in.nval;
      }
      for (int i = 0; i < n; i++) {
        in.nextToken();
        back[i] = (int) in.nval;
        for (int j = 0; j < n; j++) {
          in.nextToken();
          graph[i][j] = (int) in.nval;
        }
      }
      out.println(compute());
    }
    out.flush();
    out.close();
    br.close();
  }
  public static int compute() {
    int ans = Integer.MAX_VALUE;
    // 起始村无编号
    for (int i = 0; i < n; i++) {
      // 起始村 -> i号村  +  i号村出发所有村子都走最终回到起始村
      ans = Math.min(ans, start[i] + f(1 << i, i));
    }
    return ans;
  }
  // s : 不包含起始村的
  public static int f(int s, int i) {
    if (s == (1 << n) - 1) {
      return back[i];
    }
    if (dp[s][i] != -1) {
      return dp[s][i];
    }
    int ans = Integer.MAX_VALUE;
    for (int j = 0; j < n; j++) {
      if ((s & (1 << j)) == 0) {
        ans = Math.min(ans, graph[i][j] + f(s | (1 << j), j));
      }
    }
    dp[s][i] = ans;
    return ans;
  }
}