r****7
发帖数: 2282 | 1 有若干个盒子，每个盒子有length和width，不考虑高度。只要尺寸fit，大盒子就可以
放小盒子，但是一层只能套一个，即便还有空余；但可以多层嵌套。求最小的面积放所
有的盒子
用greedy做不出来，DP似乎是NP解啊 |
m*****k
发帖数: 731 | 2 你是说 ’回‘ ok, where the big rectangle embeds 1 smaller rectangle
‘日’ 不OK？where the big rectangle embeds 2 smaller rectangles?
【在 r****7 的大作中提到】
: 有若干个盒子，每个盒子有length和width，不考虑高度。只要尺寸fit，大盒子就可以
: 放小盒子，但是一层只能套一个，即便还有空余；但可以多层嵌套。求最小的面积放所
: 有的盒子
: 用greedy做不出来，DP似乎是NP解啊
|
h***k
发帖数: 161 | 3 刚开始没看懂。。。给这个例子跪了
【在 m*****k 的大作中提到】
: 你是说 ’回‘ ok, where the big rectangle embeds 1 smaller rectangle
: ‘日’ 不OK？where the big rectangle embeds 2 smaller rectangles?
|
l*********u
发帖数: 19053 | 4 if L
max L*max W?
【在 r****7 的大作中提到】
: 有若干个盒子，每个盒子有length和width，不考虑高度。只要尺寸fit，大盒子就可以
: 放小盒子，但是一层只能套一个，即便还有空余；但可以多层嵌套。求最小的面积放所
: 有的盒子
: 用greedy做不出来，DP似乎是NP解啊
|
m*******n
发帖数: 113 | 5 我怎么觉得应该是greedy algorithm?
先sort，选最大的盒子，套能套的最大的盒子，不能套了选剩下的最大的盒子，重复？
【在 r****7 的大作中提到】
: 有若干个盒子，每个盒子有length和width，不考虑高度。只要尺寸fit，大盒子就可以
: 放小盒子，但是一层只能套一个，即便还有空余；但可以多层嵌套。求最小的面积放所
: 有的盒子
: 用greedy做不出来，DP似乎是NP解啊
|
z******g
发帖数: 271 | 6 sort the boxes in non-increasing order by area
let sum be the area sum of all boxes
for each box b:
find the smallest box that can hold b, let it be k
if k exist:
remove k from the boxes
sum -= area(b)
return sum |
c***t
发帖数: 50 | |
c***t
发帖数: 50 | 8 请问是根据area来sort么，还有if k exist,是不是应该remove b from boxes?
【在 z******g 的大作中提到】
: sort the boxes in non-increasing order by area
: let sum be the area sum of all boxes
: for each box b:
: find the smallest box that can hold b, let it be k
: if k exist:
: remove k from the boxes
: sum -= area(b)
: return sum
|
m*******n
发帖数: 113 | 9 你这个复杂度低。确实应该从小往大，减少比较次数。
【在 z******g 的大作中提到】
: sort the boxes in non-increasing order by area
: let sum be the area sum of all boxes
: for each box b:
: find the smallest box that can hold b, let it be k
: if k exist:
: remove k from the boxes
: sum -= area(b)
: return sum
|
r****7
发帖数: 2282 | 10 这个显然不对啊，按面积sort小的能不能放进大的都不一定
【在 z******g 的大作中提到】
: sort the boxes in non-increasing order by area
: let sum be the area sum of all boxes
: for each box b:
: find the smallest box that can hold b, let it be k
: if k exist:
: remove k from the boxes
: sum -= area(b)
: return sum
|
|
|
m********8
发帖数: 44 | 11 按高度或者长度排序之后转化为 LIS， DP解之 |
p**p
发帖数: 742 | 12 没说面具小的一定可以放进大的里面啊。
但是面具大的一定放不进面积更小的里面。
按面积sort只是减少搜索的次数。
【在 r****7 的大作中提到】
: 这个显然不对啊，按面积sort小的能不能放进大的都不一定
|
r****7
发帖数: 2282 | 13 这个也不对
9*9 12*12 13*10 13*1
就挂了
【在 p**p 的大作中提到】
: 没说面具小的一定可以放进大的里面啊。
: 但是面具大的一定放不进面积更小的里面。
: 按面积sort只是减少搜索的次数。
|
r****7
发帖数: 2282 | 14 这个不错！貌似直觉是对的，哪儿有比较正式一点儿的证明么？
【在 m********8 的大作中提到】
: 按高度或者长度排序之后转化为 LIS， DP解之
|
m********8
发帖数: 44 | 15
没有找过非常正式的数学证明。。不过这个题目跟我以前算法课考试的最后一题很相似
，都是转化之后変LIS， 基本确定是对的。。
【在 r****7 的大作中提到】
: 这个不错！貌似直觉是对的，哪儿有比较正式一点儿的证明么？
|
d****n
发帖数: 233 | 16 抛个砖：
typedef struct {
int L;
int W;
} Dimension;
bool compareLW(const Dimension &l, const Dimension &r)
{
if (l.L == r.L) return l.W > r.W;
return l.L > r.L;
}
void normalize(Dimension &dimen)
{
if (dimen.L > dimen.W) {
int t = dimen.L;
dimen.L = dimen.W;
dimen.W = t;
}
}
int MinArea(vector dimens)
{
if (dimens.size() < 1) return 0;
for(int i = 0; i < dimens.size(); i++)
normalize(dimens[i]);
// Sort by Length, then Width
sort(dimens, compareByLW);
int sum1 = dimens[0].L * dimens[0].W;
int prev = 0;
for(int i = 1; i < dimens.size(); i++)
{
if(dimens[i].W > dimens[prev].W)
{
prev = i;
sum1 += dimens[i].L * dimens[i].W;
}
}
return sum
}
Complexity is O(NlogN)
【在 r****7 的大作中提到】
: 有若干个盒子，每个盒子有length和width，不考虑高度。只要尺寸fit，大盒子就可以
: 放小盒子，但是一层只能套一个，即便还有空余；但可以多层嵌套。求最小的面积放所
: 有的盒子
: 用greedy做不出来，DP似乎是NP解啊
|
z******g
发帖数: 271 | 17 是根据area来sort。如果存在k，我们就把b装进k里，k就不能再装了，总面积减小b（b
还能装）。
【在 c***t 的大作中提到】
: 请问是根据area来sort么，还有if k exist,是不是应该remove b from boxes?
|
z******g
发帖数: 271 | 18 按面积排： S={12*12, 13*10, 9*9, 13*1}, sum = 368
考虑12*12:没有能装下12*12的，跳过
考虑13*10:没有能装下13*10的，跳过
考虑9*9:能装下9*9最小的是13*10, S={12*12, 9*9, 13*1}, sum = 287
考虑13*1：能装下13*1最小的是12*12, S={9*9, 13*1}, sum=274
最小面积为274
为什么不对？
【在 r****7 的大作中提到】
: 这个也不对
: 9*9 12*12 13*10 13*1
: 就挂了
|
r****7
发帖数: 2282 | 19 13*1怎么能装进12*12里...
【在 z******g 的大作中提到】
: 按面积排： S={12*12, 13*10, 9*9, 13*1}, sum = 368
: 考虑12*12:没有能装下12*12的，跳过
: 考虑13*10:没有能装下13*10的，跳过
: 考虑9*9:能装下9*9最小的是13*10, S={12*12, 9*9, 13*1}, sum = 287
: 考虑13*1：能装下13*1最小的是12*12, S={9*9, 13*1}, sum=274
: 最小面积为274
: 为什么不对？
|
z******g
发帖数: 271 | 20 。。。看错了，那去掉最后一步
算法有问题么？
【在 r****7 的大作中提到】
: 13*1怎么能装进12*12里...
|
|
|
r****7
发帖数: 2282 | 21 最优显然是9*9放12*12，13*1放13*10啊。。。
【在 z******g 的大作中提到】
: 。。。看错了，那去掉最后一步
: 算法有问题么？
|
z******g
发帖数: 271 | 22 谢谢，明白了，算法确实错了
【在 r****7 的大作中提到】
: 最优显然是9*9放12*12，13*1放13*10啊。。。
|
b****h
发帖数: 163 | 23 greedy不对的
比如 10×10， 12×8， 7×7， 11×4，
按照你的算法7×7放到12×8里，然后11×4没盒子放了吧？
最优应该7×7放到10×10里，11×4放到12×8里
这道题用DP解，O(n^2)
【在 z******g 的大作中提到】
: 。。。看错了，那去掉最后一步
: 算法有问题么？
|
s******n
发帖数: 226 | 24 1. 就是greedy 我证明过
2. 11×4和7×7 哪个面积大？ 哪个放在外边占地方？
3. 不管怎么放， 不影响下次选的时候的available box space， 只影响最后哪些box
不会放在地上，当然每次都选择最大的
【在 b****h 的大作中提到】
: greedy不对的
: 比如 10×10， 12×8， 7×7， 11×4，
: 按照你的算法7×7放到12×8里，然后11×4没盒子放了吧？
: 最优应该7×7放到10×10里，11×4放到12×8里
: 这道题用DP解，O(n^2)
|
t*****9
发帖数: 569 | 25 转化成有向图做
【在 r****7 的大作中提到】
: 有若干个盒子，每个盒子有length和width，不考虑高度。只要尺寸fit，大盒子就可以
: 放小盒子，但是一层只能套一个，即便还有空余；但可以多层嵌套。求最小的面积放所
: 有的盒子
: 用greedy做不出来，DP似乎是NP解啊
|
b****h
发帖数: 163 | 26 按由小到大排：
11×4，7×7，12×8， 10×10
前面2个都直接放地上，处理到12×8的时候，用greedy 7*7 放入12×8里吧，继续处理
10*10,只能放外面了
最优解应该11×4放12×8里，7×7放10×10里
box
【在 s******n 的大作中提到】
: 1. 就是greedy 我证明过
: 2. 11×4和7×7 哪个面积大？ 哪个放在外边占地方？
: 3. 不管怎么放， 不影响下次选的时候的available box space， 只影响最后哪些box
: 不会放在地上，当然每次都选择最大的
|
l******6
发帖数: 340 | 27 I am not on LIS either
13*8 12 * 7 11 * 4 10 * 10 , 10 * 6 , 9 * 5
longest 13 * 8 -> 12 * 7 -> 10 * 6 -> 9 * 5 and leave 10 * 10 and 11 * 4
best 13 * 8 -> 12 * 7 -> 11 * 4 and 10 * 10 -> 10 * 6 -> 9 * 5
my algorithm:
let m = max (area[])
do a N by N map G:
G[i][j] = area[j] if mat[i] can hold mat [j]
otherwise G[i][j] = 0 (including i == j)
For a G[i][j], means mat[j] is placed in mat[i] thus save area[j] space.
Problem change to
maxmize sum (G[i][j]) that each row and each column is used exact once ( one
box exactly hold one smaller box, if it doesn't treat it as it hold itself
and save 0 space)
change G[i][j] = m - G[i][j]
problem change to minimize sum (G[i][j]) that each row and each column is
used exact once.
Then I find this link to solve this problem
http://en.wikipedia.org/wiki/Hungarian_algorithm |
s******n
发帖数: 226 | 28 1. 面积从大到小： ，10×10，，12×8， 7×7， 11×4
2. 选第一个 10x10 放在地上
3. 选剩下在地上，能放到10x10里，最大的，7x7， 同时标记7x7不在地上了已经
然后找从10x10找下一个最大的在地上的---12x8
3. 选剩下在地上，能放12x8里，最大的，11x4， 同时标记11x4不在地上了已经
然后找不到不在地上的了--- done
【在 b****h 的大作中提到】
: 按由小到大排：
: 11×4，7×7，12×8， 10×10
: 前面2个都直接放地上，处理到12×8的时候，用greedy 7*7 放入12×8里吧，继续处理
: 10*10,只能放外面了
: 最优解应该11×4放12×8里，7×7放10×10里
:
: box
|
s******d
发帖数: 9806 | 29 How about this case?
1. 20*20
2. 21*17
3. 20*16.5
4. 18*18
Your approach will put box 3 in 1, but leave box 2 and box 4.
【在 s******n 的大作中提到】
: 1. 面积从大到小： ，10×10，，12×8， 7×7， 11×4
: 2. 选第一个 10x10 放在地上
: 3. 选剩下在地上，能放到10x10里，最大的，7x7， 同时标记7x7不在地上了已经
: 然后找从10x10找下一个最大的在地上的---12x8
: 3. 选剩下在地上，能放12x8里，最大的，11x4， 同时标记11x4不在地上了已经
: 然后找不到不在地上的了--- done
|
l******6
发帖数: 340 | 30 change 12*8 to 13* 8 what you get?
【在 s******n 的大作中提到】
: 1. 面积从大到小： ，10×10，，12×8， 7×7， 11×4
: 2. 选第一个 10x10 放在地上
: 3. 选剩下在地上，能放到10x10里，最大的，7x7， 同时标记7x7不在地上了已经
: 然后找从10x10找下一个最大的在地上的---12x8
: 3. 选剩下在地上，能放12x8里，最大的，11x4， 同时标记11x4不在地上了已经
: 然后找不到不在地上的了--- done
|
|
|
b****h
发帖数: 163 | 31 把12*8换成12*9这个算法就错了
【在 s******n 的大作中提到】
: 1. 面积从大到小： ，10×10，，12×8， 7×7， 11×4
: 2. 选第一个 10x10 放在地上
: 3. 选剩下在地上，能放到10x10里，最大的，7x7， 同时标记7x7不在地上了已经
: 然后找从10x10找下一个最大的在地上的---12x8
: 3. 选剩下在地上，能放12x8里，最大的，11x4， 同时标记11x4不在地上了已经
: 然后找不到不在地上的了--- done
|
b****h
发帖数: 163 | 32 Cool. This works!
【在 l******6 的大作中提到】
: I am not on LIS either
: 13*8 12 * 7 11 * 4 10 * 10 , 10 * 6 , 9 * 5
: longest 13 * 8 -> 12 * 7 -> 10 * 6 -> 9 * 5 and leave 10 * 10 and 11 * 4
: best 13 * 8 -> 12 * 7 -> 11 * 4 and 10 * 10 -> 10 * 6 -> 9 * 5
: my algorithm:
: let m = max (area[])
: do a N by N map G:
: G[i][j] = area[j] if mat[i] can hold mat [j]
: otherwise G[i][j] = 0 (including i == j)
: For a G[i][j], means mat[j] is placed in mat[i] thus save area[j] space.
|
p**t
发帖数: 157 | 33 remove k from boxes是为了保证k不会再被用来装其他的盒子
sum -= area(b)事实上已经是把b装到了k里
【在 c***t 的大作中提到】
: 请问是根据area来sort么，还有if k exist,是不是应该remove b from boxes?
|
s******n
发帖数: 226 | 34 [13,8] [10,10] [7,7] [11,4]
[13,8] [10,10] [11,4]
248
【在 l******6 的大作中提到】
: change 12*8 to 13* 8 what you get?
|
s******n
发帖数: 226 | 35 我run出来这个：
[12,9] [10,10] [7,7] [11,4]
[12,9] [10,10] [11,4]
252
最优解是什么？
【在 b****h 的大作中提到】
: 把12*8换成12*9这个算法就错了
|
s******n
发帖数: 226 | 36 [20,20] [21,17] [18,18] [20,16]
[20,20] [21,17]
757
【在 s******d 的大作中提到】
: How about this case?
: 1. 20*20
: 2. 21*17
: 3. 20*16.5
: 4. 18*18
: Your approach will put box 3 in 1, but leave box 2 and box 4.
|
l******6
发帖数: 340 | 37 13 *8 -> 11 * 4
10 * 10 -> 7 * 7
you see 204 is enough
【在 s******n 的大作中提到】
: [13,8] [10,10] [7,7] [11,4]
: [13,8] [10,10] [11,4]
: 248
|
s******d
发帖数: 9806 | 38 I chose 16.5 for a reason, so you will pack 20*16.5 first since it is bigger
than 18*18...
【在 s******n 的大作中提到】
: [20,20] [21,17] [18,18] [20,16]
: [20,20] [21,17]
: 757
|
s******n
发帖数: 226 | 39 恩 是的 想想怎么变成DP
【在 l******6 的大作中提到】
: 13 *8 -> 11 * 4
: 10 * 10 -> 7 * 7
: you see 204 is enough
|
p**t
发帖数: 157 | 40 除了转化成LIS我确实想不出其他DP的办法。。。
但是LIS我到现在也找不到一个直观的算法
【在 s******n 的大作中提到】
: 恩 是的 想想怎么变成DP
|
|
|
s******n
发帖数: 226 | 41 目前我只想到DFS：
int minAreaBoxes(box[] b)
{
int n=b.length;
if(n==0) return 0;
if(n==1) return b[0].getArea();
Arrays.sort(b,new boxComp());
return dfs(b,new boolean[n],0);
}
int dfs(box[] b, boolean[] visited, int k)
{
if(k==b.length) return 0;
int re = visited[k]?0:b[k].getArea();
int local = 0;
for(int i=k+1;i
local +=(visited[i])?0:b[i].getArea();
for(int i=k+1;i
{
if(visited[i] || b[k].l<=b[i].l || b[k].w<=b[i].w) continue;
visited[i] = true;
local = Math.min(local,dfs(b,visited, k+1));
visited[i] = false;
}
return local+re;
}
【在 p**t 的大作中提到】
: 除了转化成LIS我确实想不出其他DP的办法。。。
: 但是LIS我到现在也找不到一个直观的算法
|
p**t
发帖数: 157 | 42 dfs这开销怕是过不了面试啊= =
我还是想一想怎么能更好的理解LIS吧
【在 s******n 的大作中提到】
: 目前我只想到DFS：
: int minAreaBoxes(box[] b)
: {
: int n=b.length;
: if(n==0) return 0;
: if(n==1) return b[0].getArea();
: Arrays.sort(b,new boxComp());
: return dfs(b,new boolean[n],0);
: }
: int dfs(box[] b, boolean[] visited, int k)
|
J*******o
发帖数: 741 | |
m*********p
发帖数: 112 | 44 正解。
【在 m********8 的大作中提到】
: 按高度或者长度排序之后转化为 LIS， DP解之
|
n****s
发帖数: 2 | 45 先按是否能装下做有向图， 然后拓扑排序。
然后建数组，第k个元素储存，前k个拓扑排序之后箱子的所有最优解，dp |
P****i
发帖数: 1362 | 46 这个做面试题也太长了吧
光判断一个盒子能不能放进另一个盒子就好多行了
【在 r****7 的大作中提到】
: 有若干个盒子，每个盒子有length和width，不考虑高度。只要尺寸fit，大盒子就可以
: 放小盒子，但是一层只能套一个，即便还有空余；但可以多层嵌套。求最小的面积放所
: 有的盒子
: 用greedy做不出来，DP似乎是NP解啊
|
t*****a
发帖数: 106 | 47 按面积排序，然后DP找LIS，剩下的元素再DP. 如果DP有tie，再分别做DP. 结果是对的
，就是复杂度比较高。
或者转成图，有conflict的box连在一起，然后找independent set. 或者Iterate找最
大的Independent set，感觉和DP差不多。。。 |
m****9
发帖数: 492 | 48 Re
【在 n****s 的大作中提到】
: 先按是否能装下做有向图， 然后拓扑排序。
: 然后建数组，第k个元素储存，前k个拓扑排序之后箱子的所有最优解，dp
|
i*********e
发帖数: 21 | 49 O(n^2)建图。每个箱子分成两个顶点，他们之间连两条有向边，一条容量为1费用为-
areaOfBox.一条容量为无穷，费用为零。入度为零的箱子特殊处理，无需分拆。箱子之
间的有向边则由是否能包含决定，容量为1，费用为零。
建源点到所有入度为零的定点，从所有出度为零的点连到汇点。容量为1，费用为0.
因为边费用<=0. 最小费用最大流的费用就是你能装进某个其他箱子中的箱子的面积总
和。
答案为所有箱子面积之和+最小费用（注意是负数）。 |
c*****m
发帖数: 271 | 50 能具体讲讲LIS和ＤＰ的思路么？尝试着写了下，没写出来。
【在 m********8 的大作中提到】
: 按高度或者长度排序之后转化为 LIS， DP解之
|
|
|
p**t
发帖数: 157 | |
