三维装箱问题C++代码

下面是三维装箱问题的 C++ 代码示例：

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int N = 20;
int n, m;
int w[N], h[N], d[N];
int v[N], ans;
bool st[N];

void dfs(int u, int area, int depth) // u:当前选取的物品编号，area:当前底面积，depth:当前高度 
{
    if (depth + v[u] > ans) return; // 剪枝：如果当前已经选取的物品总高度 + 当前物品最大高度 > 目前最优解，直接返回 
    if (area >= ans) return; // 剪枝：如果当前底面积已经大于等于最优解，直接返回 
    if (u == n) { // 如果已经遍历完所有物品 
        ans = depth; // 更新最优解 
        return;
    }
    for (int i = 0; i < m; i++) {
        if (st[i]) continue; // 如果已经选过，跳过 
        st[i] = true; // 标记已经选过 
        // 枚举当前物品的长、宽、高，计算底面积和体积 
        int nw = w[i], nh = h[i], nd = d[i];
        if (nw > nh) swap(nw, nh);
        if (nw > nd) swap(nw, nd);
        if (nh > nd) swap(nh, nd);
        for (int j = 0; j < 3; j++) {
            int na = nw * nh, nv = nw * nh * nd; // 底面积和体积 
            dfs(u + 1, area + na, depth + nd); // 递归搜索 
            swap(nw, nh); // 枚举下一个方向 
            if (j == 2) break; // 枚举完三个方向，退出 
            swap(nw, nd);
        }
        st[i] = false; // 回溯 
    }
}

int main()
{
    while (cin >> n, n) {
        cin >> m;
        for (int i = 0; i < n; i++) {
            cin >> w[i] >> h[i] >> d[i];
            v[i] = w[i] * h[i] * d[i]; // 计算体积 
        }
        ans = 0x3f3f3f3f;
        memset(st, false, sizeof st);
        dfs(0, 0, 0); // 从第0个物品，底面积为0，高度为0开始搜索 
        if (ans == 0x3f3f3f3f) puts("0"); // 如果没有找到解，输出0 
        else printf("%d\n", ans);
    }
    return 0;
}

三维装箱问题是一个 NP 难问题，因此只能使用搜索算法来求解，这里使用了 DFS 来搜索所有可能的方案，并使用剪枝来优化搜索效率。