我试图实现一个 bin-packing-type problem的解决方案，主要采用 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++ 进行编译。