小齐的数学难题,给代码(C++)


问题描述
小琪最近遇到了一个数学难题,给定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*/

img

穷举遍历呗,好像也没有别的办法

算法如下:
数据是从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