C*n
2 楼
Is it 2D bin packing?
d*u
3 楼
能不能展开说说？
【在 C*******n 的大作中提到】
: Is it 2D bin packing?
【在 C*******n 的大作中提到】
: Is it 2D bin packing?
u*g
4 楼
我觉得不是，二维背包问题的2维互相不影响，item[i]增加必然同时增加2个维度上的
费用
显然这个不是，矩形有可能只增加x轴或者只增加y轴同时另一个轴只增加了一个差值…
…比2维背包复杂多了……
【在 C*******n 的大作中提到】
: Is it 2D bin packing?
费用
显然这个不是，矩形有可能只增加x轴或者只增加y轴同时另一个轴只增加了一个差值…
…比2维背包复杂多了……
【在 C*******n 的大作中提到】
: Is it 2D bin packing?
S*t
5 楼
有意思的题目，你这个要求coding了吗？还是就讨论了下解法？大概这个问题花了多少
时间？
【在 d*******u 的大作中提到】
: 一面墙dimension: m*n, 家里有各种尺寸的照片，设计一个算法贴最多照片。
时间？
【在 d*******u 的大作中提到】
: 一面墙dimension: m*n, 家里有各种尺寸的照片，设计一个算法贴最多照片。
S*t
6 楼
一个变种问题是，设计算法贴最大面积。不过我觉得这个问题interviewer都不一定有
很好的解法。。。
【在 d*******u 的大作中提到】
: 一面墙dimension: m*n, 家里有各种尺寸的照片，设计一个算法贴最多照片。
很好的解法。。。
【在 d*******u 的大作中提到】
: 一面墙dimension: m*n, 家里有各种尺寸的照片，设计一个算法贴最多照片。
S*e
7 楼
还要看这些照片的数量吧。。。
如果数量不限，如果m×n是最小尺寸照片的整数倍，肯定全贴最小照片，
如果不是，情况比较复杂，能不能想办法用DP做？大牛指点一下吧。。。
【在 d*******u 的大作中提到】
: 一面墙dimension: m*n, 家里有各种尺寸的照片，设计一个算法贴最多照片。
如果数量不限，如果m×n是最小尺寸照片的整数倍，肯定全贴最小照片，
如果不是，情况比较复杂，能不能想办法用DP做？大牛指点一下吧。。。
【在 d*******u 的大作中提到】
: 一面墙dimension: m*n, 家里有各种尺寸的照片，设计一个算法贴最多照片。
u*g
8 楼
木有DP算法，NP-hard问题
只有近似做法或者加限制的情况下DP
【在 S********e 的大作中提到】
: 还要看这些照片的数量吧。。。
: 如果数量不限，如果m×n是最小尺寸照片的整数倍，肯定全贴最小照片，
: 如果不是，情况比较复杂，能不能想办法用DP做？大牛指点一下吧。。。
只有近似做法或者加限制的情况下DP
【在 S********e 的大作中提到】
: 还要看这些照片的数量吧。。。
: 如果数量不限，如果m×n是最小尺寸照片的整数倍，肯定全贴最小照片，
: 如果不是，情况比较复杂，能不能想办法用DP做？大牛指点一下吧。。。
j*2
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
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
blank_area-=pic.w*pic.h;
}
void deoccupy((int x, int y, img pic)
{
for(int i=x;i
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
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
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
blank_area-=pic.w*pic.h;
}
void deoccupy((int x, int y, img pic)
{
for(int i=x;i
blank_area+=pic.w*pic.h;
}
public:
int fit_wall(vector
{
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
10 楼
二维背包是个什么问题？哪里有得看？
【在 u******g 的大作中提到】
: 我觉得不是，二维背包问题的2维互相不影响，item[i]增加必然同时增加2个维度上的
: 费用
: 显然这个不是，矩形有可能只增加x轴或者只增加y轴同时另一个轴只增加了一个差值…
: …比2维背包复杂多了……
【在 u******g 的大作中提到】
: 我觉得不是，二维背包问题的2维互相不影响，item[i]增加必然同时增加2个维度上的
: 费用
: 显然这个不是，矩形有可能只增加x轴或者只增加y轴同时另一个轴只增加了一个差值…
: …比2维背包复杂多了……
f*t
11 楼
我听说过的版本是给一堆图片，要求在最小的矩形范围内贴出来。这题难得逆天了
j*2
12 楼
你说这个好像更难很多啊，在一个不规则形状旁添一个矩形，紧紧贴，得有多少种可能
啊。
【在 f*******t 的大作中提到】
: 我听说过的版本是给一堆图片，要求在最小的矩形范围内贴出来。这题难得逆天了
啊。
【在 f*******t 的大作中提到】
: 我听说过的版本是给一堆图片，要求在最小的矩形范围内贴出来。这题难得逆天了
r*e
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.
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
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;
的每个点是否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
15 楼
it's the classical floorplanning problem in eda domain. not 逆天
【在 f*******t 的大作中提到】
: 我听说过的版本是给一堆图片，要求在最小的矩形范围内贴出来。这题难得逆天了
【在 f*******t 的大作中提到】
: 我听说过的版本是给一堆图片，要求在最小的矩形范围内贴出来。这题难得逆天了
q*x
16 楼
also floorplanning problem.
【在 d*******u 的大作中提到】
: 一面墙dimension: m*n, 家里有各种尺寸的照片，设计一个算法贴最多照片。
【在 d*******u 的大作中提到】
: 一面墙dimension: m*n, 家里有各种尺寸的照片，设计一个算法贴最多照片。
相关阅读
这个怎么弄？问一下background check，如果需要international check要多久问一下那个红黑树transfer H1b从提交到收到receipt需要多长时间小白问题：才开始准备面试题，mitbbs里的面经怎么用？这样被录用的可能性有多大？继续postdoc呢还是去小的CRO? (转载)急问：接受了的offer还可以再拒掉吗老公即将三面A家，求祝福！为什么一个副总裁老说自己公司是小公司有个职位，没有相关的EXPERIENCEgoogle 面试中国科学院国家天文台射电天文技术联合实验室招聘电子技术和结(转载)来确认一下说好店面，没打电话来请教被多人轮着面的问题Design Intelligence Salary Survey 2011 (转载)两道面试题大家用哪个网站找opening？OPT 加急的一点点经验