【深度优先搜索】【组合数学】【动态规划】1467.两个盒子中球的颜色数相同的概率

作者推荐

【动态规划】【字符串】【行程码】1531. 压缩字符串

本文涉及知识点

动态规划汇总
深度优先搜索 组合数学

LeetCode1467 两个盒子中球的颜色数相同的概率

桌面上有 2n 个颜色不完全相同的球，球上的颜色共有 k 种。给你一个大小为 k 的整数数组 balls ，其中 balls[i] 是颜色为 i 的球的数量。
所有的球都已经 随机打乱顺序 ，前 n 个球放入第一个盒子，后 n 个球放入另一个盒子（请认真阅读示例 2 的解释部分）。
注意：这两个盒子是不同的。例如，两个球颜色分别为 a 和 b，盒子分别为 [] 和 ()，那么 [a] (b) 和 [b] (a) 这两种分配方式是不同的（请认真阅读示例的解释部分）。
请返回「两个盒子中球的颜色数相同」的情况的概率。答案与真实值误差在 10^-5 以内，则被视为正确答案
示例 1：
输入：balls = [1,1]
输出：1.00000
解释：球平均分配的方式只有两种：

  • 颜色为 1 的球放入第一个盒子，颜色为 2 的球放入第二个盒子
  • 颜色为 2 的球放入第一个盒子，颜色为 1 的球放入第二个盒子
    这两种分配，两个盒子中球的颜色数都相同。所以概率为 2/2 = 1 。
    示例 2：
    输入：balls = [2,1,1]
    输出：0.66667
    解释：球的列表为 [1, 1, 2, 3]
    随机打乱，得到 12 种等概率的不同打乱方案，每种方案概率为 1/12 ：
    [1,1 / 2,3], [1,1 / 3,2], [1,2 / 1,3], [1,2 / 3,1], [1,3 / 1,2], [1,3 / 2,1], [2,1 / 1,3], [2,1 / 3,1], [2,3 / 1,1], [3,1 / 1,2], [3,1 / 2,1], [3,2 / 1,1]
    然后，我们将前两个球放入第一个盒子，后两个球放入第二个盒子。
    这 12 种可能的随机打乱方式中的 8 种满足「两个盒子中球的颜色数相同」。
    概率 = 8/12 = 0.66667
    示例 3：
    输入：balls = [1,2,1,2]
    输出：0.60000
    解释：球的列表为 [1, 2, 2, 3, 4, 4]。要想显示所有 180 种随机打乱方案是很难的，但只检查「两个盒子中球的颜色数相同」的 108 种情况是比较容易的。
    概率 = 108 / 180 = 0.6 。
    提示：
    1 <= balls.length <= 8
    1 <= balls[i] <= 6
    sum(balls) 是偶数

深度优先搜索

极端情况下，8种球，6种颜色。每种球选择0到6个，共7种选择。78 约等于5e6。再加上剪支，能过。
m_iCan 记录，合法选择的可能数。
m_iAns 记录，符合题意的可能数。
注意： 从ball[i]种选择m个求，是组合 C b a l l s [ i ] m \Large C_{balls[i]}^m Cballs[i]m​

代码

核心代码

template<class Result =int >
class CCombination
{
public:
	CCombination()
	{
		m_v.assign(1, vector<Result>(1,1));
	}
	Result Get(int sel, int total)
	{
		while (m_v.size() <= total)
		{
			int iSize = m_v.size();
			m_v.emplace_back(iSize + 1, 1);
			for (int i = 1; i < iSize; i++)
			{
				m_v[iSize][i] = m_v[iSize - 1][i] + m_v[iSize - 1][i - 1];
			}
		}
		return m_v[total][sel];
	}
protected:
	vector<vector<Result>> m_v;
};

class Solution {
public:
	double getProbability(vector<int>& balls) {
		m_iN = std::accumulate(balls.begin(), balls.end(), 0) / 2;
		DFS(balls, 0, 0, 0, 0,1);
		return (double)m_iiAns / m_iiSel;
	}
	void DFS(const vector<int>& balls,int iCur,int iHasSel,int iSelAll,int iSel0,long long iiMul)
	{
		if (iHasSel == m_iN)
		{
			m_iiSel += iiMul;
			if (iSelAll == iSel0 + balls.size()- iCur )
			{//余下的球全部不选择
				m_iiAns += iiMul;
			}
			return;
		}
		if (iCur >= balls.size())
		{
			return ;
		}
		for (int curSel = 0; (curSel <= balls[iCur])&&(curSel+iHasSel <= m_iN); curSel++)
		{
			DFS(balls, iCur + 1, curSel + iHasSel, iSelAll + (curSel == balls[iCur]), iSel0 + (0 == curSel),iiMul*m_com.Get(curSel, balls[iCur]));
		}
	}
	long long m_iN, m_iiSel=0, m_iiAns=0;
	CCombination<int> m_com;
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55

测试用例

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

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]);
	}

}

int main()
{	
	vector<int> balls;
	
	{
		Solution sln;
		balls = { 1, 1 };
		auto res = sln.getProbability(balls);
		assert(abs(res -  1 ) < 0.0001);
	}

	{
		Solution sln;
		balls = { 2,1,1 };
		auto res = sln.getProbability(balls);
		assert(abs(res - 0.66667) < 0.0001);
	}

	{
		Solution sln;
		balls = { 1,2,1,2 };
		auto res = sln.getProbability(balls);
		assert(abs(res - 0.6) < 0.0001);
	}
	{
		Solution sln;
		balls = { 6, 6, 6, 6, 6, 6, 6, 6 };
		auto res = sln.getProbability(balls);
		assert(abs(res - 0.85571) < 0.0001);
	}
	
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53

动态规划

动态规划的状态表示

pre[sel][c]记录可能排列数量。sel表示第一个盒子的球数，c表示颜色差。c等于0，表示左边全选的球的数量 比 右边全先的求的数量 少6。 c = 全部在第一个盒子的颜色数- 全部在第二个盒子的颜色+6。
不在两种颜色相差8的情况：那样一个盒子为空，和n个球矛盾。
不存在颜色相差7的情况：全选7种颜色，至少有7个球。全先1种颜色顶多6个球。无法相等。
存在相差6的情况：{** 1 1 1 1 1 1 ** 3 3} 。前6个球是1，全选。
状态数：O(13n × \times ×balls.size()),n是球数的一半。
转移方程时间复杂度:O(bass[i])
故总时间复杂度O(13n × \times ×balls.size() × \times × bass[i])

class Solution {
public:
	double getProbability(vector<int>& balls) {		
		const int n = std::accumulate(balls.begin(), balls.end(), 0) / 2;
		vector<vector<long long>> pre(n + 1, vector<long long>(13, 0));
		pre[0][6] = 1;
		for (const auto& b : balls)
		{
			vector<vector<long long>> dp(n + 1, vector<long long>(13, 0));
			for (int col = 0; col < 13; col++)
			{
				for (int preSel = 0; preSel <= n; preSel++)
				{
					for (int curSel = 0; (curSel <= b) && (preSel + curSel <= n); curSel++)
					{
						int col1 = col + (curSel == b) - (curSel == 0);
						if ((col1 >= 0) && (col1 < 13))
						{
							dp[preSel + curSel][col1] += pre[preSel][col]*m_com.Get(curSel,b);
						}
					}
				}
			}
			pre.swap(dp);
		}
		long long llAns = pre.back()[6], llSel = std::accumulate(pre.back().begin(), pre.back().end(),0LL);
		return (double)llAns / llSel;
	}
	CCombination<int> m_com;
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30

2023年2月版

class Solution {
public:
double getProbability(const vector& balls) {
const int iTotal = std::accumulate(balls.begin(), balls.end(), 0);
m_c = balls.size();
vector combinations(6 + 1, vector(6 + 1, 1));
for (int i = 1; i <= 6; i++)
{
for (int j = 1; j < i; j++)
{
combinations[i][j] = combinations[i - 1][j - 1] + combinations[i - 1][j];
}
}
vector pre(13, vector(iTotal + 1));
pre[6][0] = 1;
for (int i = 0; i < balls.size(); i++)
{
vector dp(13, vector(iTotal + 1));
for (int colorDiff = 0; colorDiff < 13; colorDiff++)
{
for (int selBallNum = 0; selBallNum <= iTotal; selBallNum++)
{
if (0 == pre[colorDiff][selBallNum])
{
continue;
}
for (int k = 0; k <= balls[i]; k++)
{
int iNewColorDiff = colorDiff;
if (0 == k)
{
iNewColorDiff–;
}
if (balls[i] == k)
{
iNewColorDiff++;
}
if ((iNewColorDiff<0) || (iNewColorDiff >12))
{
continue;
}
const int iNewSelBallNum = selBallNum + k;
if ( iNewSelBallNum > iTotal)
{
continue;
}
dp[iNewColorDiff][iNewSelBallNum] += pre[colorDiff][selBallNum] * combinations[balls[i]][k];
}
}
}
pre.swap(dp);
}
double dNum = 0, dEqualNum = 0;
for (int colorDiff = 0; colorDiff < 13; colorDiff++)
{
const int selBallNum = iTotal / 2;
//for (int selBallNum = 0; selBallNum <= iTotal; selBallNum++)
{
const double dAdd = (double)pre[colorDiff][selBallNum] ;
dNum += dAdd;
if (6 == colorDiff)
{
dEqualNum += dAdd;
}
}
}
return (double)dEqualNum / dNum;
}
int m_c;
};

扩展阅读

视频课程

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

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

相关

下载

想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业

。也就是我们常说的专业的人做专业的事。 |
|如果程序是一条龙，那算法就是他的是睛|

测试环境

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

文章知识点与官方知识档案匹配，可进一步学习相关知识
算法技能树首页概览60496 人正在系统学习中
群中有博文配套源码
QQ群名片
注：本文转载自blog.csdn.net的闻缺陷则喜何志丹的文章"https://blog.csdn.net/he_zhidan/article/details/135904160"。版权归原作者所有，此博客不拥有其著作权，亦不承担相应法律责任。如有侵权，请联系我们删除。
复制链接
相关推荐
发表评论

评论记录：

未查询到任何数据！