d*******u
发帖数: 186 | 1 一面墙dimension: m*n, 家里有各种尺寸的照片，设计一个算法贴最多照片。 |
C*******n
发帖数: 49 | |
d*******u
发帖数: 186 | 3 能不能展开说说？
【在 C*******n 的大作中提到】
: Is it 2D bin packing?
|
u******g
发帖数: 89 | 4 我觉得不是，二维背包问题的2维互相不影响，item[i]增加必然同时增加2个维度上的
费用
显然这个不是，矩形有可能只增加x轴或者只增加y轴同时另一个轴只增加了一个差值…
…比2维背包复杂多了……
【在 C*******n 的大作中提到】
: Is it 2D bin packing?
|
S********t
发帖数: 3431 | 5 有意思的题目，你这个要求coding了吗？还是就讨论了下解法？大概这个问题花了多少
时间？
【在 d*******u 的大作中提到】
: 一面墙dimension: m*n, 家里有各种尺寸的照片，设计一个算法贴最多照片。
|
S********t
发帖数: 3431 | 6 一个变种问题是，设计算法贴最大面积。不过我觉得这个问题interviewer都不一定有
很好的解法。。。
【在 d*******u 的大作中提到】
: 一面墙dimension: m*n, 家里有各种尺寸的照片，设计一个算法贴最多照片。
|
S********e
发帖数: 72 | 7 还要看这些照片的数量吧。。。
如果数量不限，如果m×n是最小尺寸照片的整数倍，肯定全贴最小照片，
如果不是，情况比较复杂，能不能想办法用DP做？大牛指点一下吧。。。
【在 d*******u 的大作中提到】
: 一面墙dimension: m*n, 家里有各种尺寸的照片，设计一个算法贴最多照片。
|
u******g
发帖数: 89 | 8 木有DP算法，NP-hard问题
只有近似做法或者加限制的情况下DP
【在 S********e 的大作中提到】
: 还要看这些照片的数量吧。。。
: 如果数量不限，如果m×n是最小尺寸照片的整数倍，肯定全贴最小照片，
: 如果不是，情况比较复杂，能不能想办法用DP做？大牛指点一下吧。。。
|
j******2
发帖数: 362 | 9 我是个菜鸟，来胡乱写个DP pseudo code，大家表笑：
class pixel{ int right_blank; int below_blank;};
class img{
int h; int w; int area;
public: img(int x, int y)
{h=x;w=y;area=x*y;}
};
class wall{
pixel **matrix;
int w; int h;
int blank_area;
void init()
{
deoccupy(0,0,img(h,w));
blank_area=w*h;
}
bool can_put(int &x, int &y, img pic)
{
for(int i=0;i
for(int j=0;j
if( matrix[i][j].right_blank>=pic.w &&
matrix[i][j].below_blank>=pic.h)
{
x=i; y=j;
return true;
}
return false;
}
void occupy(int x, int y, img pic)
{
for(int i=x;i
for(int j=y;j
matrix[i][j]=pixel(0,0);
blank_area-=pic.w*pic.h;
}
void deoccupy((int x, int y, img pic)
{
for(int i=x;i
for(int j=y;j
matrix[i][j]=pixel(h-1-i,w-1-j);
blank_area+=pic.w*pic.h;
}
public:
int fit_wall(vector![]() album)
{
int max_num=0;
for(int i=0;i
{
img pic=album[i];
if(pic.area
{
int x, y;
if(can_put(x,y,pic))
{
album.delete(album.begin()+i);
occupy(x,y,pic);
max_num=max(max_num, fit_wall(temp_album)+1);
deoccupy(x,y,pic);
album.insert(album.begin+i, pic);
}
}
}
return max_num;
}
};
【在 u******g 的大作中提到】
: 木有DP算法，NP-hard问题
: 只有近似做法或者加限制的情况下DP
|
j******2
发帖数: 362 | 10 二维背包是个什么问题？哪里有得看？
【在 u******g 的大作中提到】
: 我觉得不是，二维背包问题的2维互相不影响，item[i]增加必然同时增加2个维度上的
: 费用
: 显然这个不是，矩形有可能只增加x轴或者只增加y轴同时另一个轴只增加了一个差值…
: …比2维背包复杂多了……
|
|
|
f*******t
发帖数: 7549 | 11 我听说过的版本是给一堆图片，要求在最小的矩形范围内贴出来。这题难得逆天了 |
j******2
发帖数: 362 | 12 你说这个好像更难很多啊，在一个不规则形状旁添一个矩形，紧紧贴，得有多少种可能
啊。
【在 f*******t 的大作中提到】
: 我听说过的版本是给一堆图片，要求在最小的矩形范围内贴出来。这题难得逆天了
|
r*****e
发帖数: 264 | 13 google 到的：
http://codeincomplete.com/posts/2011/5/7/bin_packing/
Here's a summary: build a binary tree. Each branch in the tree contains a
sprite. Each leaf node represents available space. Initially the tree has
just the root node, which represents all available space. To add a sprite to
the tree, search the tree for an unoccupied (leaf) node big enough to hold
the sprite. Turn that node from a leaf into a branch by setting the sprite
as the node's occupant and giving the node two children. One child
represents the remaining space to the right of the sprite; the other
represents the remaining space below the sprite and the first child. |
w********f
发帖数: 60 | 14 思路是对的, 一个小问题. 当你算can_fit()时, 应该check (i,j) ~ (i+a.w,j+a.h)中
的每个点是否available to fit the current picture. 因为有的点可能没有update.
尤其在以下情况, 大方块上的右边空白出的点的值没有update
****
* *
****
*******
* *
* *
* *
*******
【在 j******2 的大作中提到】
: 我是个菜鸟，来胡乱写个DP pseudo code，大家表笑：
: class pixel{ int right_blank; int below_blank;};
: class img{
: int h; int w; int area;
: public: img(int x, int y)
: {h=x;w=y;area=x*y;}
: };
: class wall{
: pixel **matrix;
: int w; int h;
|
q****x
发帖数: 7404 | 15 it's the classical floorplanning problem in eda domain. not 逆天
【在 f*******t 的大作中提到】
: 我听说过的版本是给一堆图片，要求在最小的矩形范围内贴出来。这题难得逆天了
|
q****x
发帖数: 7404 | 16 also floorplanning problem.
【在 d*******u 的大作中提到】
: 一面墙dimension: m*n, 家里有各种尺寸的照片，设计一个算法贴最多照片。
|
