考察: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 }
也可以直接压缩为一维.
思路二:
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 }