UVA-1252 Twenty Questions （状压dp）

小灰灰 2021-12-14 19:47 326阅读 0赞

## 题意：有n件物品，每件物品有m个特征，可以对特征进行询问，询问的结果是得知某个物体是否含有该特征，要把所有的物品区分出来（n个物品的特征都互不相同）最小需要多少次询问？ ##

## 分析：要做的是鉴别出来我心里所想的那一个物品（0-1串），所以鉴别出来一个就可以了，而又不知道心里想的是哪一个，所以取需要询问次数最多的，取每个物品（0-1串）能被鉴别出来需要的次数中次数最大的，才能保证所有物品（0-1串)在该询问次数内都能被鉴别出来，注意题目中已说明采用的是最优策略，所以不需要考虑询问的是哪几个，只考虑次数就可以了，换句话说，选出询问次数最小的，当然前提是已经保证我考虑的最坏的情况（心里想的是需要询问次数最多的）。求询问的次数，按询问的次数分阶段，询问1次是第一个阶段，询问2次是第二个阶段，……。在第i个阶段询问i次，这i次询问的特征是任意的，换句话说，询问0-1串中的元素个数是固定的（阶段），而询问哪i个位置是随意的（阶段中的决策）。每次进入下一个阶段时，添加一个元素（特征），我想的物品可能有这个特征，也可能没有，设特征为k，max\{d(s+\{k\},a+\{k\}),d(s+\{k\},a\}+1。（考虑了最坏的情况）k需要遍历，这里，已经考虑了最坏的情况，那么就可以只考虑次数了，取最小的次数。 用记忆化搜索的形式实现即可。考虑所有的i，取最小值即可。边界条件为：如果只有一个物体满足“具备集合c中的所有特征，但不具备集合k-c中的所有特征”这一条件，则d(k,c)=0，因为无须进一步询问，已经可以得到答案。取最大最小这里理解了老半天。还需要回过头再理解。 ##

## 参考：[https://www.cnblogs.com/mu-ye/p/5695675.html][https_www.cnblogs.com_mu-ye_p_5695675.html]。 ##

## 代码： ##

#include<bits/stdc++.h>
    using namespace std;
    
    const int maxn = 1 << 12;
    const int INF = 0x3f3f3f3f;
    
    string str;
    int w[130];
    int d[maxn][maxn];
    int m, n;
    
    int dp(int s, int a)
    {
        int& ans = d[s][a];
        if (ans != INF)  return ans;
        int cnt = 0;
        for (int i = 0; i<n; i++)
            //边界条件判断，如果cnt<=1，则说明能判断出来了
        if ((w[i] & s) == a)  cnt++;
        if (cnt <= 1){ d[s][a] = 0; return 0; }
    
        for (int i = 0; i<m; i++)
        {
            if (s&(1 << i))continue;
            ans = min(ans, max(dp(s | 1 << i, a | 1 << i), dp(s | 1 << i, a)) + 1);
        }
        return ans;
    }
    
    int main()
    {
        while (cin>>m>>n &&n&&m)
        {
            memset(w, 0, sizeof(w));
            memset(d, INF, sizeof(d));
            for (int i = 0; i<n; i++)
            {
                cin >> str;
                for (int j = 0; str[j]; j++)
                if (str[j] == '1')  w[i] |= (1 << j);
            }
            printf("%d\n", dp(0,0));
        }
    }

[https_www.cnblogs.com_mu-ye_p_5695675.html]: https://www.cnblogs.com/mu-ye/p/5695675.html