状压和暴力必须算出同一个数

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

状压版已给出，补全全排列暴力版 tsp_brute（用 next_permutation）。跑同一组距离，输出三样：状压结果/暴力结果/是否相同（相同输出结果一致，否则结果不一致）。

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

提交你的答案

请登录后提交答案。

去登录

← 状压解四城最短回路从暴力导出 DP 的第一步 →

更多题目

代码编辑器

语言： Ctrl + Enter 运行

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
using Item = pair<int, int>;   // (重量, 价值)

const vector<Item> ITEMS = {{3, 8}, {4, 9}, {5, 11}};

const vector<vector<int>> D4 = {{0, 5, 9, 4}, {5, 0, 3, 8}, {9, 3, 0, 6}, {4, 8, 6, 0}};

int tsp(const vector<vector<int>>& d) {
    int n = d.size();
    const int INF = 1000000000;
    vector<vector<int>> dp(1 << n, vector<int>(n, INF));
    dp[1][0] = 0;
    for (int s = 1; s < (1 << n); s++) {
        for (int u = 0; u < n; u++) {
            if (!((s >> u) & 1) || dp[s][u] == INF) continue;
            for (int v = 0; v < n; v++) {
                if ((s >> v) & 1) continue;
                int t = dp[s][u] + d[u][v];
                if (t < dp[s | (1 << v)][v]) dp[s | (1 << v)][v] = t;
            }
        }
    }
    int full = (1 << n) - 1, best = INF;
    for (int u = 1; u < n; u++) best = min(best, dp[full][u] + d[u][0]);
    return best;
}

int tsp_brute(const vector<vector<int>>& d) {
    int n = d.size();
    vector<int> order;
    for (int i = 1; i < n; i++) order.push_back(i);
    int best = 1000000000;
    // TODO: 用 next_permutation 枚举 1..n-1 的每种顺序：从 0 出发按顺序走一圈再回 0，取最短
    return best;
}

int main() {
    int a = tsp(D4), b = tsp_brute(D4);
    cout << a << "/" << b << "/" << (a == b ? "结果一致" : "结果不一致") << endl;
}

本次输入：

输出：

👩‍🏫

💬 题目评论

状压和暴力必须算出同一个数

更多题目

全部评论