第16课:枚举法(n选k问题)

潘CSP十点班

2023-12-23 9:32:13
2023-12-30 11:32:13

信息与公告

枚举法典型应用:n选k问题
(1)当k是确定的,可用循环枚举
(2)当k是变化的,可用排列枚举

n选k组合的算法思路
(1)设置一个b数组,存放k个1,n-k个0。
(2)通过全排列枚举b数组,枚举a数组n个元素中的k个元素。

for(int i=0; i<k; i++)
{
	b[i]=1;
}
do
{
	for (int i = 0; i< n; i++)     // 处理当前排列
	{
		if(b[i]==1)  // 第i个数选中
		{
                       // ...
		}
	}
}
while (prev_permutation(b + 0, b + n));    //向前枚举排列