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, 家里有各种尺寸的照片，设计一个算法贴最多照片。
相关阅读
请教大家， 这种情况我该怎么办急，什么是informational interview?local intern onsite, 就明天。。。替人问OPT 挂靠或临时工(在湾区)JOB recommendation[合集] 终于能发帖了，说说我一个月拿到EAD的事，求包子leetcode 这题insert interval怎么做？Design an algorithm to find the kth number such that the only prime factors求推荐SQL自学入门书籍刚才给google recruiter电话，问onsite结果，答复是ebay内推可以推几个职位啊提offer negotiation，对方就不理我了entry level的research scientist什么水平？facebook, google, amazon招engineering phd 具体做什么？电面完好坏都不清楚。。。求comScore面经或者tip湾区大公司招光波导和电子领域的研发牛人(不帮助申请H1和绿卡)Epic这个公司是怎么回事？软工：Intel@bayarea vs qualcomm@sandiegoimplement Blocking Queue in java