问题描述
小琪最近遇到了一个数学难题,给定n个数,从这n个数中选出k个数进行与运算,求能得到的最小值
输入格式
两个整数n和k(1<=n<=40,1<=k<=n),接下来一行输入n个整数ai(1<=ai<=260),每个整数间用空格隔开。
输出格式
从n个数中选择k个数相与,能得到的最小值。
样例输入1
8 2
238 153 223 247 111 252 253 247
样例输出1
9
样例输入2
3 2
5 6 7
样例输出2
4
改好了,你看一下:
#include<bits/stdc++.h>
using namespace std;
int a[300],min1=0x3f77,b[300],t=65535;
void combine(int n,int m,const int M )
{
for(int i=n; i>=m; i--) // 注意这里的循环范围
{
b[m-1] = i - 1;
if (m > 1)
combine(i-1,m-1,M);
else // m == 1, 输出一个组合
{
for(int j=M-1; j>=0; j--){
if(j==M-1)
t=a[b[j]];
else
t=t&a[b[j]];
}
if(t<min1)
min1=t;
}
}
}
int main()
{
int i,n,k,j,t=0;
cin>>n>>k;
for(i=0; i<n; i++)
{
cin>>a[i];
}
combine(n,k,k);
cout<<min1;
return 0;
}
/*8 2
238 153 223 247 111 252 253 247*/
穷举遍历呗,好像也没有别的办法
算法如下:
数据是从0-260,共9位。 作一个[N*K]的临时结果矩阵。
1。从9位开始朝下,找出前导0最多的数,假如是一个和多个,把这几个数标号的1列置1。假如从这位开始没有前导0,继续下一位
2。从1步那位,把所有的数前面所有位置0,重复1步骤,
3。执行K次,可能K次未完成,就到0位了,说明K个数内有部分数与的结果为0。
矩阵于下
238 153 223 247 111 252 253 243 101 241
11101110 10011001 11011111 11110111 01101111 11111100 11111101 11110011 01100101 11110001
0 0 0 0 1 0 0 0 1 0
0 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 0
0 1 0 0 0 0 0 0 0 1
1 0 0 0 0 1 0 0 0 0
根据矩阵,
k=2:111&101
k=3 : 111&153&101
K=4 : 111&153&101&241