빈 포장 솔루션 :이 문제는 어떻게됩니까?

Question

a bin-packing-type problem에 대한 해결책을 구현하려고 시도했습니다. 대부분 described by Dietrich Epp입니다. 나는 하스켈을하지 않았으므로 C++로 무언가를 썼다.

특정 숫자 (36)보다 낮은 벽 너비의 경우, 내 프로그램과 하스켈 프로그램은 동일한 결과를 제공합니다. 폭이 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 
}; 

당신은 당신이 16해야 할 수도 있습니다

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

에 몇 계승 누락! 너의 한계를 위해. 추가로

   , 
    87178291200, 
    1307674368000, 
    20922789888000 

을 적절한 위치에 추가하십시오.