080状压dp-上

k个样本
状态有2的k次方个
状压dp往往样本数据量都不大 20个以内

题目一

/ 我能赢吗
// 给定两个整数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;
	}

}

题目二

// 火柴拼正方形
// 你将得到一个整数数组 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;
	}

}

题目三

// 划分为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;
	}

题目四

// 售货员的难题 - 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;
	}

}