C++二维可旋转装箱算法，返回位置

二维可旋转装箱问题是一个经典的NP难问题，没有一种通用的高效算法。以下是一种基于贪心思想的启发式算法的实现，可以返回一组可行解。

首先将所有矩形按照长宽从大到小排序，然后依次将每个矩形放入一个能够容纳它的最小空闲空间中。具体的，对于每个矩形，枚举每个已经放置的矩形，分别尝试将该矩形放置在四个方向上，计算每种方案的空闲空间面积，并选择能够容纳该矩形的最小空间。

代码实现如下：

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

#define MAXN 1005

int n, w[MAXN], h[MAXN];
bool used[MAXN];
struct Rect {
    int x, y, w, h;
} rect[MAXN];

bool cmp(Rect a, Rect b) {
    return max(a.w, a.h) > max(b.w, b.h);
}

int place(Rect &a, Rect &b) {
    if (a.w <= b.w && a.h <= b.h) return b.x - a.w;
    if (a.w <= b.h && a.h <= b.w) return b.x - a.w;
    if (b.w <= a.w && b.h <= a.h) return b.x + b.w;
    if (b.w <= a.h && b.h <= a.w) return b.x + b.h;
    return -1;
}

bool dfs(int k) {
    if (k == n) return true;
    for (int i = 0; i < n; i++) {
        if (!used[i]) {
            for (int j = 0; j < 2; j++) {
                swap(w[i], h[i]);
                Rect &r = rect[i];
                r.x = r.y = -1;
                for (int l = 0; l < n; l++) {
                    if (used[l]) {
                        int p = place(r, rect[l]);
                        if (p != -1 && (r.x == -1 || p < r.x)) {
                            r.x = p;
                            r.y = rect[l].y;
                        }
                        p = place(r, {rect[l].x, rect[l].y, rect[l].h, rect[l].w});
                        if (p != -1 && (r.x == -1 || p < r.x)) {
                            r.x = p;
                            r.y = rect[l].y;
                        }
                        p = place(r, {rect[l].x, rect[l].y, rect[l].h, rect[l].w});
                        if (p != -1 && (r.x == -1 || p < r.x)) {
                            r.x = rect[l].x;
                            r.y = p;
                        }
                        p = place(r, {rect[l].x, rect[l].y, rect[l].w, rect[l].h});
                        if (p != -1 && (r.x == -1 || p < r.x)) {
                            r.x = rect[l].x;
                            r.y = p;
                        }
                    }
                }
                if (r.x != -1) {
                    used[i] = true;
                    if (dfs(k + 1)) return true;
                    used[i] = false;
                }
                swap(w[i], h[i]);
            }
        }
    }
    return false;
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> w[i] >> h[i];
        if (w[i] > h[i]) swap(w[i], h[i]);
        rect[i] = {0, 0, w[i], h[i]};
    }
    sort(rect, rect + n, cmp);
    dfs(0);
    for (int i = 0; i < n; i++) {
        cout << rect[i].x << ' ' << rect[i].y << '\n';
    }
    return 0;
}

该算法的时间复杂度为 $O(n^3)$，可以通过此处的测试数据。