0

我在一家公司的物流部门工作，最近我们一直在努力缩小我们使用的不同包装选项的数量。

我拥有所有必要的产品数据，例如长度、宽度、高度、体积以及销售数据。

所以我在想是否可以使用一种算法来对不同体积的产品进行聚类，也许还可以考虑哪些尺寸卖得最多，以确定哪些盒子尺寸是理想的。（考虑到产品的销售频率是次要的，因此这不是绝对必要的）

我想要的是我可以给算法一个我想要多少不同盒子大小的数量，并且算法应该确定在哪里放置限制，以便我们拥有的每个产品都有一个解决方案。优化的目标是尽可能减少浪费的体积，同时不使用超过设定数量的不同盒子。

另外需要注意的是，产品的方向和每盒的数量是固定的，因此无需确定如何包装产品以及理想情况下有多少产品进入一个盒子或类似的东西。

什么样的算法可以用于这样的问题，我有什么选择来编程它们？我正在考虑使用 Matlab，但也愿意接受其他可能的选择。我想对其进行编程，而不是简单地使用像 SPSS 这样的现有程序。

提前谢谢，如果我的英语不是最好的，请原谅我，我不是母语人士。

4

1 回答 1

0

以下 C++ 程序将为小型实例找到最佳解决方案。对于 10 个输入框尺寸，每个尺寸在 1..100 范围内随机选择，对于任何数量为 1..10 的框尺寸可供选择，它会在我的计算机上几秒钟内计算出答案。对于 15 个输入框大小，大约需要 10 秒。对于 20 个输入框大小，我可以在大约 3 分钟内计算多达 4 个选定的框大小，内存成为问题（它使用了大约 3GB）。我不得不增加链接器的默认堆栈大小以避免堆栈溢出。

#include <iostream>
#include <algorithm>
#include <vector>
#include <array>
#include <map>
#include <set>
#include <functional>
#include <climits>

using namespace std;

ostream& operator<<(ostream& os, array<int, 3> a) {
    return os << '(' << a[0] << ", " << a[1] << ", " << a[2] << ')';
}

template <int N>
long long vol(array<int, N> b) {
    return static_cast<long long>(b[0]) * b[1] * b[2];
}

template <int N, int M>
bool fits(array<int, N> a, array<int, M> b) {
    return a[0] <= b[0] && a[1] <= b[1] && a[2] <= b[2];
}

// Compares first by volume, then lexicographically.
struct CompareByVolumeDesc {
    bool operator()(array<int, 3> a, array<int, 3> b) const {
        return vol(a) > vol(b) || vol(a) == vol(b) && a < b;
    }
};

vector<array<int, 3>> candSizes;

struct State {
    vector<array<int, 4>> req;
    int n;
    int k;

    // Needed for map<>
    bool operator<(State const& other) const {
        return make_tuple(n, k, req) < make_tuple(other.n, other.k, other.req);
    }
} dummy = { {}, -1, -1 };

map<State, pair<int, State>> memo;

// Compute the minimum volume required for the given list of box sizes if we use exactly k of the first n candidate box sizes.
pair<long long, State> solve(State const& s) {
    if (empty(s.req)) return { 0, dummy };
    if (s.k == 0 || s.k > s.n) return { LLONG_MAX / 4, dummy };
    auto previousAnswer = memo.find(s);
    if (previousAnswer != end(memo)) return (*previousAnswer).second;

    // Try using the nth candidate box size.
    int nFitting = 0;
    vector<array<int, 4>> notFitting;
    for (auto r : s.req) {
        if (fits(r, candSizes[s.n - 1])) {
            nFitting += r[3];
        } else {
            notFitting.push_back(r);
        }
    }

    pair<long long, State> solution;
    solution.second = { s.req, s.n - 1, s.k };
    solution.first = solve(solution.second).first;
    if (nFitting > 0) {
        State useNth = { notFitting, s.n - 1, s.k - 1 };
        long long useNthVol = nFitting * vol(candSizes[s.n - 1]) + solve(useNth).first;
        if (useNthVol < solution.first) solution = { useNthVol, useNth };
    }
    memo[s] = solution;
    return solution;
}

void printOptimalSolution(State s) {
    while (!empty(s.req)) {
        State next = solve(s).second;
        if (next.k < s.k) cout << candSizes[s.n - 1] << endl;
        s = next;
    }
}

int main(int argc, char** argv) {
    int n, k;
    cin >> n >> k;
    vector<array<int, 4>> requestedBoxSizes;
    set<int> lengths, widths, heights;
    for (int i = 0; i < n; ++i) {
        array<int, 4> d;        // d[3] is actually the number of requests for this box size
        cin >> d[0] >> d[1] >> d[2] >> d[3];
        sort(begin(d), begin(d) + 3, std::greater<int>());
        requestedBoxSizes.push_back(d);

        lengths.insert(d[0]);
        widths.insert(d[1]);
        heights.insert(d[2]);
    }

    // Generate all candidate box sizes
    for (int l : lengths) {
        for (int w : widths) {
            for (int h : heights) {
                array<int, 3> cand = { l, w, h };
                sort(begin(cand), end(cand), std::greater<int>());
                candSizes.push_back(cand);
            }
        }
    }

    sort(begin(candSizes), end(candSizes), CompareByVolumeDesc());
    candSizes.erase(unique(begin(candSizes), end(candSizes)), end(candSizes));
    cout << "Number of candidate box sizes: " << size(candSizes) << endl;
    State startState = { requestedBoxSizes, static_cast<int>(size(candSizes)), k };
    long long minVolume = solve(startState).first;
    cout << "Minimum achievable volume using " << k << " box sizes: " << minVolume << endl;
    cout << "Optimal set of " << k << " box sizes:" << endl;
    printOptimalSolution(startState);
    return 0;
}

示例输入：

15 5
100 61 35 27
17 89 96 47
31 69 30 55
37 23 39 9
94 11 48 19
38 17 29 36
63 79 80 36
59 52 37 51
86 63 54 7
32 30 11 26
50 88 51 5
74 70 33 14
67 46 4 79
83 94 89 58
65 42 37 69

示例输出：

Number of candidate box sizes: 2310
Minimum achievable volume using 5 box sizes: 124069460
Optimal set of 5 box sizes:
(94, 48, 11)
(69, 52, 37)
(100, 89, 35)
(88, 79, 63)
(94, 89, 83)

如果有兴趣，我会解释这背后的算法。这比考虑 k 个候选框大小的所有可能组合要好，但效率不是很高。

于 2021-05-07T16:13:37.223 回答