Re: 为什么中国人喜欢当苦逼？ (转载)# Joke - 肚皮舞运动
s*i
1 楼
一面墙dimension: m*n, 家里有各种尺寸的照片，设计一个算法贴最多照片。
好像别的公司也问到了。
简单的挖去右下角的dp，剩下的子问题不再是矩形，所以不是简单的两维dp就能解决的
。求问大牛们如何解答？
谢谢！
好像别的公司也问到了。
简单的挖去右下角的dp，剩下的子问题不再是矩形，所以不是简单的两维dp就能解决的
。求问大牛们如何解答？
谢谢！
g*0
2 楼
【 以下文字转载自 Military 讨论区 】
发信人: OXGBIX (牛英九), 信区: Military
标 题: Re: 为什么中国人喜欢当苦逼？
发信站: BBS 未名空间站 (Wed Sep 11 20:28:12 2013, 美东)
还好，比说信了主之后就牛逼了要强
发信人: OXGBIX (牛英九), 信区: Military
标 题: Re: 为什么中国人喜欢当苦逼？
发信站: BBS 未名空间站 (Wed Sep 11 20:28:12 2013, 美东)
还好，比说信了主之后就牛逼了要强
p*u
3 楼
剩下2个矩形，不是吗？
【在 s*****i 的大作中提到】
: 一面墙dimension: m*n, 家里有各种尺寸的照片，设计一个算法贴最多照片。
: 好像别的公司也问到了。
: 简单的挖去右下角的dp，剩下的子问题不再是矩形，所以不是简单的两维dp就能解决的
: 。求问大牛们如何解答？
: 谢谢！
【在 s*****i 的大作中提到】
: 一面墙dimension: m*n, 家里有各种尺寸的照片，设计一个算法贴最多照片。
: 好像别的公司也问到了。
: 简单的挖去右下角的dp，剩下的子问题不再是矩形，所以不是简单的两维dp就能解决的
: 。求问大牛们如何解答？
: 谢谢！
m*2
4 楼
是说付萍吗？
d*e
5 楼
照片是无限多么？
如果照片是无限多，还是二维dp吧
【在 s*****i 的大作中提到】
: 一面墙dimension: m*n, 家里有各种尺寸的照片，设计一个算法贴最多照片。
: 好像别的公司也问到了。
: 简单的挖去右下角的dp，剩下的子问题不再是矩形，所以不是简单的两维dp就能解决的
: 。求问大牛们如何解答？
: 谢谢！
如果照片是无限多，还是二维dp吧
【在 s*****i 的大作中提到】
: 一面墙dimension: m*n, 家里有各种尺寸的照片，设计一个算法贴最多照片。
: 好像别的公司也问到了。
: 简单的挖去右下角的dp，剩下的子问题不再是矩形，所以不是简单的两维dp就能解决的
: 。求问大牛们如何解答？
: 谢谢！
r*o
6 楼
不对吧，如果说剩下两个矩形，那么两个矩形交界的地方怎么算？
就算用取2种分法的max，还是有漏掉一些解吧？
dp[m][n] = 1 + Math.max(dp[m-a][b] + dp[m][n-b],
dp[m-a][n] + dp[a, n-b]);
就算用取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
7 楼
对了，如果照片不是无限多的话，那么：
就需要决定recursive的顺序？ 以及要用一个数组去保存已经visited的照片，to
prevent conflict?
就需要决定recursive的顺序？ 以及要用一个数组去保存已经visited的照片，to
prevent conflict?
z*g
8 楼
如果想成剩下3个矩形呢？
g*y
9 楼
没有什么问题啊，看不出来漏了什么解。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]);
:
【在 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
10 楼
照片可以贴在跨越边界的地方，比如跨越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]);
:
子问题是一个六边形，这个六边形问题不是简单的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
11 楼
我也是觉得两个矩形交界的地方导致不能用这种简单的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]);
:
【在 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
12 楼
照片不管怎么跨越边界，只要不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里有道题就是那样设计的
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
13 楼
这是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
先问问是否有额外的条件，照片大小、张数之类的
如果额外条件的话，应该无法在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
14 楼
USACO 里有一块板子贴一堆东西的题 不过是算面积和周长的
h*u
15 楼
这个属于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.
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
16 楼
这个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.
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
17 楼
请问题目里，照片的尺寸和个数是不是已经给定的？
【在 s*****i 的大作中提到】
: 一面墙dimension: m*n, 家里有各种尺寸的照片，设计一个算法贴最多照片。
: 好像别的公司也问到了。
: 简单的挖去右下角的dp，剩下的子问题不再是矩形，所以不是简单的两维dp就能解决的
: 。求问大牛们如何解答？
: 谢谢！
【在 s*****i 的大作中提到】
: 一面墙dimension: m*n, 家里有各种尺寸的照片，设计一个算法贴最多照片。
: 好像别的公司也问到了。
: 简单的挖去右下角的dp，剩下的子问题不再是矩形，所以不是简单的两维dp就能解决的
: 。求问大牛们如何解答？
: 谢谢！
h*u
18 楼
有道理。除了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.
: 就是说必须从一边割到另外一边（不能割到中间就停），原题里没有这个约束。
个题目只是允许最多一个。
这个也不属于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
19 楼
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.
'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
20 楼
Still can't get the solution. Any more hints?
Thanks
Thanks
g*g
21 楼
---------
--|
|
------|
假设每种尺寸无限：
减下去右 {（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)表示。
--|
|
------|
假设每种尺寸无限：
减下去右 {（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
22 楼
我觉得，Operations Research这个最top的journal上的题，就不可能拿来出面试题了
吧。
吧。
相关阅读
盲人画家白灵居然演过美版西游记的观世音 (转载)Re: 感谢三得四 (转载)90多昼夜编写代码40余万行，你们这些码农简直弱爆了。[HWPT]挪威发现古怪海草 网友调侃是特朗普头发种植基地 (转载)无机点笑话：我们都中了老邢的器人计了欢欢乐乐 Z现在还有人集邮么？器人发帖主要是缺乏海外生活背景，完全是国内东西Re: 给大家介绍几部反应美国最贱最穷的人的生活的电视剧 (转载)我发誓以后再也不会被人用枪指着我的头张召忠将军：中国四个小时就能打垮日本世上有几种咪咪和鸡鸡？极品笑话[转]中国的空姐空少对比美国的空妈空叔，搞不懂为什么这样健身103 (转载)老型真是从善如流，现在新ID都在转段子。这是什么原因的车祸？Re: 想说几句关于马加爵杀人的真相 (转载)一些笑话