s*****i
发帖数: 32 | 1 一面墙dimension: m*n, 家里有各种尺寸的照片，设计一个算法贴最多照片。
好像别的公司也问到了。
简单的挖去右下角的dp，剩下的子问题不再是矩形，所以不是简单的两维dp就能解决的
。求问大牛们如何解答？
谢谢！ |
p*u
发帖数: 136 | 2 剩下2个矩形，不是吗？
【在 s*****i 的大作中提到】
: 一面墙dimension: m*n, 家里有各种尺寸的照片，设计一个算法贴最多照片。
: 好像别的公司也问到了。
: 简单的挖去右下角的dp，剩下的子问题不再是矩形，所以不是简单的两维dp就能解决的
: 。求问大牛们如何解答？
: 谢谢！
|
d********e
发帖数: 239 | 3 照片是无限多么？
如果照片是无限多，还是二维dp吧
【在 s*****i 的大作中提到】
: 一面墙dimension: m*n, 家里有各种尺寸的照片，设计一个算法贴最多照片。
: 好像别的公司也问到了。
: 简单的挖去右下角的dp，剩下的子问题不再是矩形，所以不是简单的两维dp就能解决的
: 。求问大牛们如何解答？
: 谢谢！
|
r**********o
发帖数: 50 | 4 不对吧，如果说剩下两个矩形，那么两个矩形交界的地方怎么算？
就算用取2种分法的max，还是有漏掉一些解吧？
dp[m][n] = 1 + Math.max(dp[m-a][b] + dp[m][n-b],
dp[m-a][n] + dp[a, n-b]);
|
r**********o
发帖数: 50 | 5 对了，如果照片不是无限多的话，那么：
就需要决定recursive的顺序？ 以及要用一个数组去保存已经visited的照片，to
prevent conflict? |
z******g
发帖数: 271 | |
g**********y
发帖数: 14569 | 7 没有什么问题啊，看不出来漏了什么解。USACO里有道题就是那样设计的
【在 r**********o 的大作中提到】
: 不对吧，如果说剩下两个矩形，那么两个矩形交界的地方怎么算？
: 就算用取2种分法的max，还是有漏掉一些解吧？
: dp[m][n] = 1 + Math.max(dp[m-a][b] + dp[m][n-b],
: dp[m-a][n] + dp[a, n-b]);
:
|
s*****i
发帖数: 32 | 8 照片可以贴在跨越边界的地方，比如跨越dp[m-a][b] 和 dp[m][n-b]交接的那条线。
子问题是一个六边形，这个六边形问题不是简单的max(dp[m-a][b] + dp[m][n-b], dp[
m-a][n] + dp[a, n-b])就能解决的。也就是说子问题跟原问题已经不一样了。
发信人: gloomyturkey (一只郁闷的火鸡), 信区: JobHunting
标 题: Re: 求问G面试题，非普通的DP
发信站: BBS 未名空间站 (Wed Dec 25 16:18:03 2013, 美东)
没有什么问题啊，看不出来漏了什么解。USACO里有道题就是那样设计的
【在 r**********o 的大作中提到】
: 不对吧，如果说剩下两个矩形，那么两个矩形交界的地方怎么算？
: 就算用取2种分法的max，还是有漏掉一些解吧？
: dp[m][n] = 1 + Math.max(dp[m-a][b] + dp[m][n-b],
: dp[m-a][n] + dp[a, n-b]);
:
|
s*****i
发帖数: 32 | 9 我也是觉得两个矩形交界的地方导致不能用这种简单的DP。
【在 r**********o 的大作中提到】
: 不对吧，如果说剩下两个矩形，那么两个矩形交界的地方怎么算？
: 就算用取2种分法的max，还是有漏掉一些解吧？
: dp[m][n] = 1 + Math.max(dp[m-a][b] + dp[m][n-b],
: dp[m-a][n] + dp[a, n-b]);
:
|
g**********y
发帖数: 14569 | 10 照片不管怎么跨越边界，只要不overlap, 就一定落在定义的四个矩形里的某一个。
dp[
【在 s*****i 的大作中提到】
: 照片可以贴在跨越边界的地方，比如跨越dp[m-a][b] 和 dp[m][n-b]交接的那条线。
: 子问题是一个六边形，这个六边形问题不是简单的max(dp[m-a][b] + dp[m][n-b], dp[
: m-a][n] + dp[a, n-b])就能解决的。也就是说子问题跟原问题已经不一样了。
: 发信人: gloomyturkey (一只郁闷的火鸡), 信区: JobHunting
: 标 题: Re: 求问G面试题，非普通的DP
: 发信站: BBS 未名空间站 (Wed Dec 25 16:18:03 2013, 美东)
: 没有什么问题啊，看不出来漏了什么解。USACO里有道题就是那样设计的
|
|
|
M**********s
发帖数: 8 | 11 这是2D bin packing问题吧？这样的话就是NP-hard
先问问是否有额外的条件，照片大小、张数之类的
如果额外条件的话，应该无法在polynomial time求最佳解
可以构思一些一些heuristic approach
题外话，游戏常需要把很多不同大小的textures压在同一张texture
就是要用类似的方法
但optimize的目标不一样：
游戏要用最少的「牆壁」，而这题是只有一面牆壁要贴最多的照片。
不知道我记得的跟您说的是不是同一题
USACO 1.4.1 Packing Rectangles 那道题只有4个矩形，brute force就解掉了
但如果有30张大小不同的照片恰好可以塞在一个大rectangle中，可能是找不出最佳解的
我觉得2D DP不可行，原因如先前有人提到，就是无法model不同大小照片造成的縫隙
另外如果他真的是NP-hard，也显然不可能reduce成2D DP |
b*********h
发帖数: 103 | 12 USACO 里有一块板子贴一堆东西的题 不过是算面积和周长的 |
h*****u
发帖数: 109 | 13 这个属于2D knapsack problem. 有DP算法，复杂度为O(LW(n+L+W)) 。见
http://www.cs.kent.edu/~parallel/papers/ulm_wmpp04.pdf
P.C. Gilmore and R.E. Gomory, Multistage cutting stock
problems of two or more dimensions, Operations Research,
13:94-120, 1965. |
w*******s
发帖数: 138 | 14 这个paper里的方法有一个额外的约束：
This cutting problem allows only recursive side-to-side or guillotine cuts o
f the knapsack.
就是说必须从一边割到另外一边（不能割到中间就停），原题里没有这个约束。
【在 h*****u 的大作中提到】
: 这个属于2D knapsack problem. 有DP算法，复杂度为O(LW(n+L+W)) 。见
: http://www.cs.kent.edu/~parallel/papers/ulm_wmpp04.pdf
: P.C. Gilmore and R.E. Gomory, Multistage cutting stock
: problems of two or more dimensions, Operations Research,
: 13:94-120, 1965.
|
h****t
发帖数: 184 | 15 请问题目里，照片的尺寸和个数是不是已经给定的？
【在 s*****i 的大作中提到】
: 一面墙dimension: m*n, 家里有各种尺寸的照片，设计一个算法贴最多照片。
: 好像别的公司也问到了。
: 简单的挖去右下角的dp，剩下的子问题不再是矩形，所以不是简单的两维dp就能解决的
: 。求问大牛们如何解答？
: 谢谢！
|
h*****u
发帖数: 109 | 16 有道理。除了guillotine cut，Gilmore and Gomory 还允许 multiple items，但是这
个题目只是允许最多一个。
这个也不属于multi-dimensional knapsack, 因为不是简单的相加关系。
我找到最相关的是：An exact algorithm for general, orthogonal, two-
dimensional knapsack problems, European Journal of Operational Research 83 (
1995) 39-56。但是也不是DP.
感觉如果要表征solution，需要把已经剩余区域的所有极点(extreme points)都记录下
来。如此，怎么设计DP?
o
【在 w*******s 的大作中提到】
: 这个paper里的方法有一个额外的约束：
: This cutting problem allows only recursive side-to-side or guillotine cuts o
: f the knapsack.
: 就是说必须从一边割到另外一边（不能割到中间就停），原题里没有这个约束。
|
j*********g
发帖数: 36 | 17 If we do not allow infinitely many copies for every photo dimension, then it
's NP-hard. Reduce subset sum to it.
If infinitely many copies are allowed, I think there is a greedy+DP solution
. Start by removing all "dominated" dimensions, i.e. axb dominates cxd if a
<=c and b<=d. |
l********r
发帖数: 140 | 18 Still can't get the solution. Any more hints?
Thanks |
g*****g
发帖数: 212 | 19 ---------
--|
|
------|
假设每种尺寸无限：
减下去右 {（x1,y1）,(x2,y2)}，有两种分割：
1） {(0，0),(x2,y1)} {(0,y1),(x1,y2)}
2) {(0,0),(x1,y2)} {(x1,0),(x2,y1)}
是否可以如此
DP是求 max( 1),2) ) +1
DP 基本元素是 矩形（长和宽），所以可以用一个matrix(n X m)表示。 |
c*****e
发帖数: 67 | 20 我觉得，Operations Research这个最top的journal上的题，就不可能拿来出面试题了
吧。 |
