首页 > 其他 > 详细

P3052 [USACO12MAR]摩天大楼里的奶牛Cows in a Skyscraper [模拟退火]

时间:2019-02-02 22:35:09      阅读:282      评论:0      收藏:0      [点我收藏+]

P3052 [USACO12MAR]摩天大楼里的奶牛Cows in a Skyscraper

给出n个物品,体积为w[i],现把其分成若干组,要求每组总体积<=W,问最小分组。(n<=18)

想状压dp正解是不可能的,这辈子都不可能的

如果物品的分组是连续的,那么就是个小学组问题了:直接遍历贪心搞即可。

据说还有dp方法:\(dp[i]\)为前\(i\)个物品的最小分组,如果某段区间的和大于\(W\),那么就转移一下。利用前缀和并不难写。

像这道题这种无序分组的问题,其实可以通过各种打乱顺序化成连续分组问题来解决。

没错,随机算法来了!在这里我们用模拟退火随机打乱序列。

void SA() {
    const double delta = 0.99;
    const double eps = 1e-7;
    for(double T = 5555; T > eps; T *= delta) {
        // 模拟退火打乱序列过程
        ll x = rand() % n + 1, y = rand() % n + 1;// 随机两个下标
        while(x == y) x = rand() % n + 1, y = rand() % n + 1;// 不要一样
        std::swap(a[x], a[y]);// 换了
        ll newans = getans();
        ll DE = ans - newans;
        if(DE > 0) {
            ans = newans;// 比原来好
        } else if(exp(DE / T) * RAND_MAX > rand()) {// 右边是rand()别写错了
            // 一定概率接受低谷(什么都不用做。。。)
        } else {
            std::swap(a[x], a[y]);// 换回来
        }
    }
}

随机打乱序列的还有std::ramdon_shuffle函数,但是可能比较难控制这种降温。

这道题的玄学调参是这样的:

\(w\)乘以\(1.05\)或者比这个小一点点的浮点数。不知道为什么

P3052 [USACO12MAR]摩天大楼里的奶牛Cows in a Skyscraper [模拟退火]

原文:https://www.cnblogs.com/Garen-Wang/p/10349307.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!