考察:IDA* or 状压+背包dp
思路一:
n个物品包,每个都可以用二进制表示,f[i][j]表示前i个物品组成j状态最少需要多少包,状态转移方程为
int t = min(f[i-1][j|candy[i]],f[i-1][j]+1);
f[i][j|candy[i]] = min(t,f[i][j|candy[i]]);
f[i][j] = min(f[i-1][j],f[i][j]);//不选第i件
但是直接这么写会TLE,这里有一个状态是无用的状态,就是f[i-1][j|candy[i]],这个状态如果!=INF,说明i-1件就已经凑成状态z(z=j|candy[i]),此时两种情况:
- z==candy[i],毫无疑问此时只选第i件更优
- z!=candy[i],但是f[i-1][z]!=INF,说明i-1件能凑成z,而i件也能凑成z.f[i-1][j|candy[i]]的效果实际与第三行代码相同.因为j|candy[i]一定也会被遍历到.但是第三行代码是不能省略的.
1 #include <iostream>
2 #include <cstring>
3 using namespace std;
4 const int N = 110,M = 1<<20,INF = 0x3f3f3f3f;
5 int n,m,k,candy[N],f[2][M+1];
6 int main()
7 {
8 scanf("%d%d%d",&n,&m,&k);
9 for(int i=1;i<=n;i++)
10 for(int j=1;j<=k;j++)
11 {
12 int x; scanf("%d",&x);
13 candy[i]|=1<<x-1;
14 }
15 memset(f,0x3f,sizeof f);
16 f[0&1][0] = 0;
17 int all = (1<<m)-1;
18 for(int i=1;i<=n;i++)
19 for(int j=0;j<=all;j++)
20 {
21 if(f[i-1&1][j]<=n)
22 {
23 f[i&1][j|candy[i]] = min(f[i&1][j|candy[i]],f[i-1&1][j]+1);
24 f[i&1][j] = min(f[i-1&1][j],f[i&1][j]);//不选第i件
25 }
26 }
27 if(f[n&1][all]<=m) printf("%d\n",f[n&1][all]);
28 else printf("-1\n");
29 return 0;
30 }
状压dp
也可以直接压缩为一维.
思路二:
IDA*算法,dfs的顺序是找到一个当前没有的口味,枚举有这个口味的糖包.再dfs下一个没有的口味.这里还需要三个优化.
- 迭代加深:从小到大枚举可能的答案.如果枚举的答案不符合继续++枚举下一个
- 估价函数:计算当前状态到目标状态至少还需要几步,如果枚举的答案<估价函数,那么可以直接返回.
- 每次都选择没有的口味中,有此口味最少的包数的那一列.
其中1与2是IDA*的算法.
1 #include <iostream>
2 #include <cstring>
3 #include <cstdio>
4 #include <vector>
5 using namespace std;
6 const int N = 25,M = 1<<20;
7 int logs[M+1],n,m,k,all;
8 vector<int> v[N];
9 int lowbit(int x)
10 {
11 return x&-x;
12 }
13 int h(int st)
14 {
15 int res = 0;
16 for(int i=all-st;i;i-=lowbit(i))
17 {
18 int c = logs[lowbit(i)];
19 res++;
20 for(int j=0;j<v[c].size();j++)
21 i&=~v[c][j];
22 }
23 return res;
24 }
25 bool dfs(int dep,int now)
26 {
27 if(!dep||h(now)>dep) return now==all;
28 int t = -1;
29 for(int i=all-now;i;i-=lowbit(i))
30 {
31 int c = logs[lowbit(i)];
32 if(t==-1||v[t].size()>v[c].size()) t = c;
33 }
34 for(int i=0;i<v[t].size();i++)
35 if(dfs(dep-1,now|v[t][i])) return 1;
36 return 0;
37 }
38 int main()
39 {
40 scanf("%d%d%d",&n,&m,&k);
41 all = (1<<m)-1;
42 for(int i=0;i<=20;i++) logs[1<<i] = i;
43 for(int i=1;i<=n;i++)
44 {
45 int st = 0;
46 for(int j=1;j<=k;j++)
47 {
48 int x; scanf("%d",&x);
49 st|=1<<x-1;
50 }
51 for(int j=0;j<m;j++)
52 if(st>>j&1) v[j].push_back(st);
53 }
54 int dep = 1;
55 while(dep<=m&&!dfs(dep,0)) dep++;
56 if(dep>m) puts("-1");
57 else printf("%d\n",dep);
58 return 0;
59 }
DFS优化