题解 P1460 【健康的荷斯坦奶牛 Healthy Holsteins 】

下面那篇二进制枚举子集题解被我叉了！~~我第一次交的代码也被自己叉了~~ ### 整体思路 因为每种饲料只有选或不选两种状态，所以可以用二进制枚举子集，共2^g个子集，每种子集需要gv的时间判断是否合法，所以时间复杂度是gv*2^g，因为这题数据很小，可以过。 ### 字典序的保证 考虑用二进制来枚举子集，右数第i位为0代表不选饲料g+1-i（这里比较特殊，原因待会儿说），为1代表选饲料g+1-i，选的饲料个数就是1的数量，那么从2^g-1枚举到0，第一个遇到的最优解即为字典序最小的。因为：（这里可以自己想清楚，证明感觉略繁琐） - 假设有两个最优解a和b（a的字典序小于b），它们都有x个1 - 从二进制表示中比较方案的字典序即比较： 1. 若a的左数第一个1比b的左数第一个1靠左则a的字典序大，反之b的字典序大 2. 若位置一样，则比较左数第二个1的位置 3. 继续比较，直至不同 - 可以看出，在a的字典序小于b时，a本身是大于b的，即a先于b被枚举到 为什么要用第i位表示选不选饲料g+1-i而不是饲料i呢？因为二进制枚举的时候是固定高位不变先变低位，只有把编号小的饲料放在二进制的高位上才能保证第一个遇到的解是字典序最小的 ### 数饲料个数 第一个遇到只能保证字典序小，不能保证饲料个数少，所以还要数饲料的个数 数饲料个数就是在二进制表示中数1的个数，代码如下： ``` int count(int x) { int out=0; while (x) { out+=x&1; x>>=1; } return out; } ``` ### 完整代码 ``` #include <iostream> #include <cstdio> #include <cstring> using namespace std; int v,need[30],g,a[20][30],ans,minn=0x7fffffff,t[30]; int count(int x); int main() { int i,j,k; bool flag; cin>>v; for (i=0;i<v;++i) { cin>>need[i]; } cin>>g; for (i=1;i<=g;++i) { for (j=0;j<v;++j) { cin>>a[i][j]; } } for (i=(1<<g)-1;i>=0;--i) //二进制枚举子集 { if (count(i)<minn) //若当前子集的饲料数大于等于当前的最优解则当前子集一定不是答案 { memset(t,0,sizeof(t)); for (j=0;j<g;++j) { if ((1<<j)&i) //i的右数第j+1位为1代表饲料g-j在当前枚举的子集中 { for (k=0;k<v;++k) { t[k]+=a[g-j][k]; } } } flag=true; for (j=0;j<v;++j) //判断当前方案是否合法 { if (t[j]<need[j]) { flag=false; break; } } if (flag) //因为已经判断过当前子集饲料数小于当前最优解，若当前方案合法则直接更新最优解 { minn=count(i); ans=i; } } } cout<<minn; for (i=g-1;i>=0;--i) //输出方案 { if ((1<<i)&ans) { cout<<" "<<g-i; } } return 0; } int count(int x) //数1的个数 { int out=0; while (x) { out+=x&1; x>>=1; } return out; } ```