动态规划、状态压缩

写了2种算法，都主要是状态压缩，不过第二种应该只能算是状态压缩后的暴力，称不上dp。

算法1

这题很关键的一个点是想到使用状态压缩，然后用动态规划来做，如果能想到的话其实不是很困难。不过我看算法tag那里写的是DFS和IDA*，估计是暴力直接搜加一些优化吧。

首先因为只有20种口味的糖果，所以能用二进制状态压缩存入每一包的糖果口味情况。

接着，逐一遍历所有口味i，并且用一个map类型的mc数据结构来存放所有满足i-1种口味的包装情况（包装所含的口味和包数）。

最后，从mc中取出该包装，若该包装已有第i口味，则继续存入，若该包装无第i口味，则遍历所有糖果包，查看是否有第i口味的包，有则存入。这里要注意的是判重，记录糖果包数最小的就行。在遍历mc的过程中，要记录一个flag，若没有一个包满足当前口味i，则flag=false，输出结果。

C++ 代码

#include<iostream>
#include<map>
using namespace std;

int n,m,k;
int pc[105];

int main(){
    cin>>n>>m>>k;
    for(int i=0;i<n;i++){
        int pack=0;
        for(int j=0;j<k;j++){   // 状态压缩成二进制，存入每一包包含的口味情况
            int candy;
            cin>>candy;
            candy--;
            pack|=(1<<candy);
        }
        pc[i]=pack;
    }

    map<int,int> mc;    // 用于存放满足的组合情况
    mc[0]=0;
    bool flag=true;
    for(int i=0;i<m;i++){   // 逐一遍历所有口味
        map<int,int> t;
        flag=false; // 判断是否该口味能凑出
        for(auto p : mc){   // 从以满足的所有组合中查看是否新的口味也满足
            int a=p.first, b=p.second;
            if((1<<i)&p.first){ // 若该组合有新的口味
                flag=true;
                if(t.count(a)) t[a]=min(t[a], b);
                else t[a]=b;
            }
            else{   // 若该组合无新的口味，则需遍历所有糖果包查看是否加一包糖果能满足
                for(int j=0;j<n;j++){
                    if(pc[j]&(1<<i)){
                        flag=true;
                        if(t.count(a|pc[j])) t[a|pc[j]]=min(t[a|pc[j]], b+1);
                        else t[a|pc[j]]=b+1;
                    }
                }
            }
        }
        if(!flag) break;
        mc=t;
    }
    if(flag){   // 若存在，则遍历所有组合，输出最小包数
        int res=1<<30;
        for(auto p : mc){
            res=min(res, p.second);
        }
        cout<<res;
    }
    else cout<<"-1";

    return 0;
}

算法2

同样先状态压缩，然后每次取出一包糖果，遍历更新所有状态。感觉像是暴力枚举。。。

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

const int maxn=100+5;
const int maxs=(1<<20)+10, inf=1<<30;
int f[maxs];
int s[maxn];
int n,m,k;

int main(){
    scanf("%d%d%d",&n,&m,&k);
    int i,j,state=(1<<m)-1;

    for(i=0;i<=state;i++) f[i]=inf;
    for(i=0;i<n;i++){
        int pack=0;
        for(j=0;j<k;j++){
            int candy;
            scanf("%d",&candy);
            candy--;
            pack|=(1<<candy);
        }
        s[i]=pack;
        f[pack]=1;
    }

    for(i=0;i<n;i++){ 
        for(j=0;j<=state ;j++){
            if(f[j]==inf) continue;
            f[ j|s[i] ] = min( f[ j|s[i] ] , 1+f[j]  );
        }
    }
    if(f[state]==inf) printf("-1");
    else printf("%d",f[state]);
    return 0;
}