algorithm - 装箱解决方案 : what's going on with this?

Question

我已尝试实现 a bin-packing-type problem 的解决方案, 主要是在途中 described by Dietrich Epp .我还不会用 Haskell，所以我用 C++ 写了一些东西。

对于小于特定数字 (36) 的墙宽，我的程序和 Haskell 程序给出相同的结果。对于任何 36 个单位宽或更宽的墙，我的结果要低得多。我怀疑我的解决方案是否正确，因为另一张海报在这里有很多“代表”。我认为问题在于我的位矩阵中 1 的数量比应有的少得多。

#include <vector>
#include <iostream>
#include <algorithm>

const int NARROW_W = 6;     // 3
const int WIDE_W = 9;       // 4.5

const int MIN_WALL_W = 6;   // 3
const int MAX_WALL_W = 96;  // 48
const int MIN_WALL_H = 1;
const int MAX_WALL_H = 10;

// precomputed factorials for finding # of combos
static const long long fact[] =
{
    1,
    1,
    2,
    6,
    24,
    120,
    720,
    5040,
    40320,
    362880,
    3628800,
39916800,
479001600,
6227020800
};

using namespace std;

typedef vector<unsigned long long> LongVec;
typedef vector< vector<int> > IntMat;

LongVec operator * (const IntMat &a, const LongVec &b); // O(n^2)

int main(int argc, char** argv)
{
    int i, j, k;
    int width, height;
    int lcm; // Lowest Common Multiple
    int narrowc, widec;
    bool valid;
    unsigned rowc;
    IntMat bit_mat, gap_vecs, block_vecs;
    vector<int> gaps, blocks;
    vector<int>::iterator it;
    unsigned long long result;
    LongVec vec_res;

    if (argc < 3)
    {
        cerr << "Usage: " << argv[0] << " [width] [height]\n";
        exit(EXIT_FAILURE);
    }
    width = (int) (strtod(argv[1], NULL) * 2);
    height = (int) strtod(argv[2], NULL);
    if (width < MIN_WALL_W || width > MAX_WALL_W)
    {
        cerr << "Width out of range\n";
        exit(EXIT_FAILURE);
    }
    if (height < MIN_WALL_H || height > MAX_WALL_H)
    {
        cerr << "Height out of range\n";
        exit(EXIT_FAILURE);
    }

    // see if valid row is possible
    // by removing narrows and adding wides until width is reached
    narrowc = width / NARROW_W;
    widec = 0;
    valid = false;
    if (width % NARROW_W > 0)
    {
        while (narrowc > 0 && !valid)
        {
            narrowc--;
            widec = 0;
            do
                widec++;
            while ((widec * WIDE_W) + (narrowc * NARROW_W) < width);
            if ((widec * WIDE_W) + (narrowc * NARROW_W) == width)
                valid = true;
        }
    }
    else valid = true;
    if (!valid)
    {
        cout << 0;
        exit(EXIT_SUCCESS);
    }

    // find valid rows
    lcm = WIDE_W;
    while (lcm % WIDE_W != 0 || lcm % NARROW_W != 0)
        lcm++;
    rowc = 0;
    while (narrowc >= 0)
    {
        rowc += (unsigned) (fact[narrowc + widec] /
            (fact[narrowc] * fact[widec]));

        block_vecs.reserve(rowc);
        gap_vecs.reserve(rowc);

        blocks.clear();
        for (j = 0; j < narrowc; j++)
        {
            blocks.push_back(NARROW_W);
        }
        for (j = 0; j < widec; j++)
        {
            blocks.push_back(WIDE_W);
        }
        block_vecs.push_back(blocks);

        gap_vecs.push_back(blocks);
        for (j = 1; j < gap_vecs.back().size() - 1; j++)
        {
            gap_vecs.back().at(j) += gap_vecs.back().at(j - 1);
        }
        gap_vecs.back().pop_back();

        if (widec > 0 && narrowc > 0)
        {
            while (next_permutation(blocks.begin(), blocks.end()))
            {
                block_vecs.push_back(blocks);

                gap_vecs.push_back(blocks);
                for (j = 1; j < gap_vecs.back().size() - 1; j++)
                {
                    gap_vecs.back().at(j) += gap_vecs.back().at(j - 1);
                }
                gap_vecs.back().pop_back();
            }
        }

        narrowc -= lcm / NARROW_W;
        widec += lcm / WIDE_W;
    }

    // fill bit matrix
    bit_mat.reserve(rowc);
    vector<int> v(gap_vecs.at(0).size() * 2);
    for (i = 0; i < rowc; i++)
    {
        gaps.clear();
        bit_mat.push_back(gaps);
        gaps = gap_vecs.at(i);
        for (j = 0; j < rowc; j++)
        {
            //v.clear();
            it = set_intersection(gaps.begin(), gaps.end(),
                    gap_vecs.at(j).begin(), gap_vecs.at(j).end(), v.begin());
            if ((int) (it - v.begin()) != 0)
            {
                bit_mat.back().push_back(0);
            }
            else
            {
                bit_mat.back().push_back(1);
            }
        }
    }

    // multiply vector of 1's by bit matrix (height - 1) times
    vec_res.assign(rowc, 1);
    for (i = 0; i < height - 1; i++)
    {
        vec_res = bit_mat * vec_res;
    }
    result = 0;
    for (i = 0; i < vec_res.size(); i++)
        result += vec_res.at(i);

    cout << result;

    exit(EXIT_SUCCESS);
}

LongVec operator * (const IntMat &a, const LongVec &b)
{
    int i, j;
    int m = a.size();
    int n = b.size();

    LongVec result(m);

    for (i = 0; i < m; i++)
    {
        result[i] = 0;
        for (j = 0; j < n; j++)
        {
            result[i] += a[i][j] * b[j];
        }
    }
    return result;
}

我怀疑，如果这没有提供正确的解决方案，则 set_intersection() 函数没有做它应该做的事情(看看两组“差距”索引之间是否有任何匹配)。有任何想法吗？我在 Mac OS X 10.8 上使用 g++ 进行编译。

Answer 1

// precomputed factorials for finding # of combos
static const long long fact[] =
{
    1,
    1,
    2,
    6,
    24,
    120,
    720,
    5040,
    40320,
    362880,
    3628800,
    39916800,
    479001600,
    6227020800
};

您缺少一些阶乘，在

   rowc += (unsigned) (fact[narrowc + widec] /
        (fact[narrowc] * fact[widec]));

您可能需要 16 个!为了你的极限。添加

              ,
    87178291200,
    1307674368000,
    20922789888000

在适当的地方。