迭代加深搜索 get ！

A4paper · 2018-09-13 20:50:47 · 个人记录

练习：

传送门

其实这道题是想用模拟退火做的。。。

枚举桶数，再搜索奶牛数，

如果能装下所有奶牛，则得出正解，

如果不能，继续枚举

int n,W;
int tot[MAXN],w[MAXN];

bool dfs(int bull, int num)
{
    for(int i=1;i<=num && i<=bull;i++)
        if(tot[i]+w[bull] <= W)
        {
            tot[i] += w[bull];
            if(bull == n)       return 1;
            if(dfs(bull+1,num)) return 1;
            tot[i] -= w[bull];
        }
    return 0;
}

int main(void)
{
    cin >> n >> W;
    for(int i=1;i<=n;i++)
        cin >> w[i];
    for(int i=1;i<=n;i++)
    {
        memset(tot,0,sizeof tot);
        if(dfs(1,i))
        {
            cout << i;
            return  0;
        }
    }
    return 0;
}