最优要试多少个子集

👁️ 1 人浏览 💬 0 人评论 ❤️ 添加收藏

暴力求最优要一个个试子集。数一数它试了多少个、贪心只看了多少条边，再算出七个点一共有多少个子集。

（本题用 g++ -std=c++17 -O0 编译。）

提交你的答案

请登录后提交答案。

去登录

← 两张图的近似比把 A 归到 B 是在做什么 →

更多题目

代码编辑器

语言： Ctrl + Enter 运行

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

using Edge = pair<int, int>;

int greedy_vc(const vector<Edge>& edges) {    // 贪心：两头都没被盖住就把两头都收下，返回收了几个点
    vector<bool> used(16, false);
    int cnt = 0;
    for (auto [a, b] : edges) {
        if (!used[a] && !used[b]) {
            used[a] = used[b] = true;
            cnt += 2;
        }
    }
    return cnt;
}

int opt_vc(const vector<Edge>& edges, int n) {  // 暴力：从小到大试每种规模，第一个能盖住所有边的就是最优
    for (int k = 0; k <= n; k++) {
        for (int mask = 0; mask < (1 << n); mask++) {
            if (__builtin_popcount(mask) != k) continue;
            bool ok = true;
            for (auto [a, b] : edges) {
                if (!((mask >> a) & 1) && !((mask >> b) & 1)) { ok = false; break; }
            }
            if (ok) return k;
        }
    }
    return n;
}

const vector<Edge> E = {{0, 1}, {0, 2}, {1, 2}, {1, 3}, {3, 4}, {4, 5}, {5, 6}, {4, 6}};
const vector<Edge> E2 = {{0, 1}, {2, 3}, {4, 5}};

int opt_steps(const vector<Edge>& edges, int n) {
    int steps = 0;
    for (int k = 0; k <= n; k++) {
        for (int mask = 0; mask < (1 << n); mask++) {
            if (__builtin_popcount(mask) != k) continue;
            steps++;
            bool ok = true;
            for (auto [a, b] : edges) {
                if (!((mask >> a) & 1) && !((mask >> b) & 1)) { ok = false; break; }
            }
            if (ok) return steps;
        }
    }
    return steps;
}

int main() {
    // TODO: 暴力试了多少个子集（opt_steps）、贪心看了多少条边（E.size()）、七个点的子集一共多少个（1 << 7）
    int brute_steps = -1, fast_steps = -1, all_subsets = -1;
    cout << brute_steps << "/" << fast_steps << "/" << all_subsets << endl;
}

本次输入：

输出：

👩‍🏫

💬 题目评论

最优要试多少个子集

更多题目

全部评论