品物の並び替え #C++

品物の並び替え
愚直で解けるけど暇なので色々遊んでみた

自分の解法(340ms)

並び方を全通り試すのが$O(N!)$
品物のスコアを判定するのが$O(NM)$
なので全体の計算量は$O(N!NM)$となる。
$N=9, M=72$が最大なので当てはめると計算ステップは$235146240$回となる。
大体$10^8$回くらいだからギリギリだと思ったけど332msで解けてしまった。$10^8$回のステップが1秒ってのはあてにしすぎない方がいいのかも。

コード

#include <bits/stdc++.h>
using namespace std;

#define int long long
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }

int N, M;
int item1[100];
int item2[100];
int score[100];

signed main() {
    cin >> N >> M;
    for (int i = 0; i < M; i++) {
        cin >> item1[i] >> item2[i] >> score[i];
    }

    // 並び方を定義する配列
    vector<int> v(N);
    iota(v.begin(), v.end(), 0);

    int ans = 0;
    do {
        int sum = 0; // この並びの時の合計スコア

        // その並びになってるかを全て調べる
        for (int i = 0; i < M; i++) {
            int cnt = 0;
            for (int j = 0; j < N; j++) {
                if (cnt == 0 and v[j] == item1[i]) {
                    cnt++;
                }
                if (cnt == 1 and v[j] == item2[i]) {
                    cnt++;
                }
            }
            // その並びになってたらスコアを足す
            if (cnt == 2) {
                sum += score[i];
            }
        }

        chmax(ans, sum);
    } while (next_permutation(v.begin(), v.end()));

    cout << ans << endl;

    return 0;
}

ちょっと改善する(17ms)

2次元配列で持てば判定部分が$O(N^2)$になる
よって全体的な計算量は$O(N!N^2)$となる
N=9が最大なので最大の計算ステップは$29393280$回となる。大体$10^7$回なので余裕で間に合う
これ頭いい。普通に思いつかなくないか？

コード

#include <bits/stdc++.h>
using namespace std;

#define int long long

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }

int N, M;
int item[100][100]; // item1, item2, scoreをこれひとつにまとめた

signed main() {
    cin >> N >> M;
    for (int i = 0; i < M; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        item[a][b] = c;
    }

    vector<int> v(N);
    iota(v.begin(), v.end(), 0);

    int ans = 0;
    do {
        int sum = 0;

        for (int i = 0; i < N; i++) {
            for (int j = i+1; j < N; j++) {
                sum += item[v[i]][v[j]];
            }
        }

        chmax(ans, sum);
    } while (next_permutation(v.begin(), v.end()));

    cout << ans << endl;

  return 0;
}

DPを書いてみる(5ms)

とりあえず再帰で書いてみる。普通の再帰じゃなくてbitDPに寄せた再帰。コードはこんな感じ
再帰がかけたらあとはメモ化するだけ
計算量はよくわからない。けど早い
ループでDPを回すのはこんな感じのコード

コード

#include <bits/stdc++.h>
using namespace std;

#define int long long

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }

int N, M;
int item[100][100];
int dp[1<<9];

int rec(int mask) {
    if (mask >= (1<<N)-1) return 0;
    if (dp[mask] != -1) return dp[mask];

    int ret = 0;
    for (int i = 0; i < N; i++) { // iは新しく選ぶやつ
        // iを選んだことがあるなら飛ばす
        if (mask & (1 << i)) continue;

        // 新しく選ぶやつに関するスコアを計算
        int score = 0;
        for (int j = 0; j < N; j++) {
            if (mask & (1 << j)) {
                score += item[j][i];
            }
        }

        chmax(ret, rec(mask | (1 << i)) + score);
    }

    return dp[mask] = ret;
}

signed main() {
    cin >> N >> M;
    for (int i = 0; i < M; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        item[a][b] = c;
    }

    fill(dp, dp+(1<<9), -1);

    int ans = rec(0);

    cout << ans << endl;

    return 0;
}

要点

$N!$をしたい気持ちになったらbitDPができるって強い人が言ってた