http://218.28.19.228:8081/cogs/index.php书架二题解

书架2的问题可以转化为求集合中所有子集的问题（每个牛堆是一个子集）用牛高度的加和减书架高度，求最小值。

本题有两种方法

1.搜索 2.状态压缩

状态压缩求子集：

用一个二进制数表示是否选取某个集合元素（1为子集中有此位置元素，0为没有），每次+1，枚举所有子集

下面是状态压缩代码

#include<bits/stdc++.h> 
using namespace std;
int er[25]={0};
int ii=0;
void erj(int a)
{
    while(a!=0)
    {
        er[ii]=a%2;
        a/=2;
        ii++;
    }
}
int main()
{
    freopen("shelf2.in","r",stdin);
    freopen("shelf2.out","w",stdout);
    int n,b;
    cin>>n>>b;
    int a=pow(2,n+1);
    int n1[25]={0};
    for(int i=0;i<n;i++)cin>>n1[i];
    int sum=0,ans=9999999;
    for(int i=0;i<a;i++)
    {
        erj(i);
        for(int j=0;j<ii;j++)
        {
            if(er[j])sum+=n1[j];
        }
        if(sum>=b)
        {
            ans=min(ans,sum-b);
        }
        sum=0;
        ii=0;
        memset(er,0,sizeof(er));
    }
    cout<<ans;
    return 0;
}

 更新时间：

  2001.9.11