当前位置：首页 > article >正文

小猫爬山 dfs/状压

article 2024/9/25 10:40:18

题意

形如：n个物品各有体积。一次至多运m体积，最少运几次。

例题：

https://codeforces.com/gym/104787/problem/J

https://www.luogu.com.cn/problem/P3052

https://www.luogu.com.cn/problem/P10483

解法

dfs

void dfs(int cur, int cnt) { //第几个物品，已运几次
    if (cnt >= ans) return;
    if (cur == m) {
        ans = cnt;
        return;
    }
    for (int i = 0; i < cnt; i++) { //枚举之前空隙
        if (sum[i] + v[cur] <= w) {
            sum[i] += v[cur];
            dfs(cur + 1, cnt);
            sum[i] -= v[cur];
        }
    }
    sum[cnt] = v[cur];
    dfs(cur + 1, cnt + 1);
    sum[cnt] = 0;
}

状压dp

枚举子集的写法，复杂度3^m

ll dp[1 << 18], s[1 << 18];
void fun() {
    int k = (1 << m);
    for (int i = 1; i < k; i++) {
        for (int j = 0; j < m; j++) {
            if (i & (1 << j)) s[i] += v[j];
        }
    }
    dp[0] = 0;
    for (int i = 1; i < k; i++) dp[i] = 1e9;
    for (int i = 1; i < k; i++) {
        for (int j = i; j; j = (j - 1) & i) { //枚举子集
            if (s[j] > w) continue;
            dp[i] = min(dp[i], dp[i - j] + 1);
        }
    }
    cout << dp[k - 1] << endl;
}