推荐|【状态压缩枚举回溯】1601. 最多可达成的换楼请求数目

本文涉及知识点

LeetCode1601. 最多可达成的换楼请求数目

我们有 n 栋楼，编号从 0 到 n - 1 。每栋楼有若干员工。由于现在是换楼的季节，部分员工想要换一栋楼居住。
给你一个数组 requests ，其中 requests[i] = [fromi, toi] ，表示一个员工请求从编号为 fromi 的楼搬到编号为 toi 的楼。
一开始所有楼都是满的，所以从请求列表中选出的若干个请求是可行的需要满足每栋楼员工净变化为 0 。意思是每栋楼离开的员工数目等于该楼搬入的员工数数目。比方说 n = 3 且两个员工要离开楼 0 ，一个员工要离开楼 1 ，一个员工要离开楼 2 ，如果该请求列表可行，应该要有两个员工搬入楼 0 ，一个员工搬入楼 1 ，一个员工搬入楼 2 。
请你从原请求列表中选出若干个请求，使得它们是一个可行的请求列表，并返回所有可行列表中最大请求数目。

示例 1：
输入：n = 5, requests = [[0,1],[1,0],[0,1],[1,2],[2,0],[3,4]]
输出：5
解释：请求列表如下：
从楼 0 离开的员工为 x 和 y ，且他们都想要搬到楼 1 。
从楼 1 离开的员工为 a 和 b ，且他们分别想要搬到楼 2 和 0 。
从楼 2 离开的员工为 z ，且他想要搬到楼 0 。
从楼 3 离开的员工为 c ，且他想要搬到楼 4 。
没有员工从楼 4 离开。
我们可以让 x 和 b 交换他们的楼，以满足他们的请求。
我们可以让 y，a 和 z 三人在三栋楼间交换位置，满足他们的要求。
所以最多可以满足 5 个请求。
示例 2：
输入：n = 3, requests = [[0,0],[1,2],[2,1]]
输出：3
解释：请求列表如下：
从楼 0 离开的员工为 x ，且他想要回到原来的楼 0 。
从楼 1 离开的员工为 y ，且他想要搬到楼 2 。
从楼 2 离开的员工为 z ，且他想要搬到楼 1 。
我们可以满足所有的请求。
示例 3：

输入：n = 4, requests = [[0,3],[3,1],[1,2],[2,0]]
输出：4

提示：
1 <= n <= 20
1 <= requests.length <= 16
requests[i].length == 2
0 <= fromi, toi < n

回溯

最大回溯层次（结束条件）：m = requests.length。
回溯选择列表：达成当前请求忽略当前请求
处理路径（状态）；根据当前满足的数量，更新返回值。
参数：已经回溯层次leve，已经达成请求数has。vChange各楼净变化量。
初始调用：BackTrack(0,0)
无剪枝。
时间复杂度： O(2^m)

回溯代码

核心代码

class Solution {
public:
	int maximumRequests(const int n, vector<vector<int>>& requests) {
		int iRet = 0;
		vector<int> vChange(n);
		function<void(int, int)> BackTrack = [&](int leve, int has) {
			if (requests.size() == leve) {
				if (n == std::count(vChange.begin(), vChange.end(), 0)) {
					iRet = max(iRet, has);					
				}
				return;
			}
			BackTrack(leve + 1, has);
			vChange[requests[leve][0]]++;
			vChange[requests[leve][1]]--;
			BackTrack(leve + 1, has+1);
			vChange[requests[leve][0]]--;
			vChange[requests[leve][1]]++;
		};
		BackTrack(0, 0);
		return iRet;
	}
};

测试用例

template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
	if (v1.size() != v2.size())
	{
		assert(false);
		return;
	}
	for (int i = 0; i < v1.size(); i++)
	{
		assert(v1[i] == v2[i]);
	}
}

template<class T>
void Assert(const T& t1, const T& t2)
{
	assert(t1 == t2);
}

int main()
{
	int n;
	vector<vector<int>> requests;
	{
		Solution slu;
		n = 5, requests = { {0,0} };
		auto res = slu.maximumRequests(n, requests);
		Assert(1, res);
	}
	{
		Solution slu;
		n = 5, requests = { {0,1},{1,0},{0,1},{1,2},{2,0},{3,4} };
		auto res = slu.maximumRequests(n, requests);
		Assert(5, res);
	}
	{
		Solution slu;
		n = 3, requests = { {0,0},{1,2},{2,1} };
		auto res = slu.maximumRequests(n, requests);
		Assert(3, res);
	}
	{
		Solution slu;
		n = 4, requests = { {0,3},{3,1},{1,2},{2,0} };
		auto res = slu.maximumRequests(n, requests);
		Assert(4, res);
	}

	
}

2023年4月

class Solution {
public:
int maximumRequests(int n, vector& requests) {
m_c = requests.size();
m_iMaskNum = 1 << m_c;
std::queue que;
std::unordered_set setHasDo;
que.emplace(m_iMaskNum - 1);
while (que.size())
{
const int iMask = que.front();
que.pop();
vector vNums(n);
for (int iBit = 0; iBit < m_c; iBit++)
{
if (iMask & (1 << iBit))
{
vNums[requests[iBit][0]]–;
vNums[requests[iBit][1]]++;
const int iNewMask = iMask ^ (1 << iBit);
if (!setHasDo.count(iNewMask))
{
que.push(iNewMask);
setHasDo.emplace(iNewMask);
}
}
}
bool bVilid = std::count(vNums.begin(), vNums.end(), 0) == n;
if (bVilid)
{
return bitcount(iMask);
}
}
return 0;
}
int m_c;
int m_iMaskNum;
};

扩展阅读

视频课程

有效学习：明确的目标及时的反馈拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

我想对大家说的话
《喜缺全书算法册》以原理、正确性证明、总结为主。
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。

文章知识点与官方知识档案匹配，可进一步学习相关知识

算法技能树首页概览61211 人正在系统学习中

群中有博文配套源码

QQ群名片

【状态压缩枚举回溯】1601. 最多可达成的换楼请求数目