发两个测试给大家玩玩把 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>PDA - 掌中宝

发两个测试给大家玩玩把

发两个测试给大家玩玩把# PDA - 掌中宝

g*02012-09-24 07:09

1 楼

Given a list of presentations with begin and end time that all need to
use a conference room. We want to optimize the utilization of the room
by allowing maximum hours of the conference room being used.
Note: Not optimizing for the maximum number of presentations (This
would be the greedy algorithm from the CLRS book).
Any idea?

l*n2012-09-24 07:09

2 楼

对应于geekbench里面得memory和stream测试. stream测试比较确认, geekbench的网站
给出了相应的reference, 去相应网站下载了源码重新编译就是了. memory测试我估计
它是主要来源于这个测试程序: cachebench http://icl.cs.utk.edu/projects/llcbench/cachebench.html. Read/Write Sequential对应于cachebench的Read/Write Benchmark(hand tuned version), Stdlib Write/Copy对应于memset(), memcpy(), 然后自己增加了一个Stdlib Allocate.
STREAM: http://www.mediafire.com/download.php?j8miua5isyeigqh
MEMORY: http://www.mediafire.com/download.php?qkrgk3yej7hirfm
运行得话, ssh到android设备或者开个终端模拟器. STREAM测试直接就敲./stream就可
以了, MEMORY测试的话: ./cachebench -rwspt

d*d2012-09-24 07:09

3 楼

I guess dp will do

g*e2012-09-24 07:09

4 楼

背包问题

【在 g******0 的大作中提到】

: Given a list of presentations with begin and end time that all need to
: use a conference room. We want to optimize the utilization of the room
: by allowing maximum hours of the conference room being used.
: Note: Not optimizing for the maximum number of presentations (This
: would be the greedy algorithm from the CLRS book).
: Any idea?

c*n2012-09-24 07:09

5 楼

could somebody prove that we can generate an optimal solution if occupied
hours (end time - begin time) are used for greedy choices?

s*y2012-09-24 07:09

6 楼

[0,2] [3,12][14,15] [3,7][8,15]
greedy will be [0,2] [3,12][14,15]
but best should be [0,2][3,7][8,15]

【在 c*******n 的大作中提到】

: could somebody prove that we can generate an optimal solution if occupied
: hours (end time - begin time) are used for greedy choices?

c*n2012-09-24 07:09

7 楼

Nice work!
then we should try DP

【在 s*****y 的大作中提到】

: [0,2] [3,12][14,15] [3,7][8,15]
: greedy will be [0,2] [3,12][14,15]
: but best should be [0,2][3,7][8,15]

g*y2012-09-24 07:09

8 楼

写了一个ugly的实现，想法是把presentation按结束时间排序。最后结束时间T，M[0..
T]记录时间0..t的最大利用值。
M[A(n,1)] = max{A(n,1)-A(n,0)+max(M[0..A(n,0)]), max(M[0..A(n,1)])}
程序应该可以简化，要输出选择的presentation, 数据结构也要改。
public void maxUse(List list) {
Collections.sort(list, new Comparator() {
public int compare(int[] a, int[] b) {
return a[1] - b[1];
}
});

int N = list.size();
int T = list.get(N-1)[1];
int[] max = new int[T+1];

for (int i=0; iint[] a = list.get(i);
int v1 = getMax(max, a[1]);
int v2 = a[1] - a[0] + getMax(max, a[0]-1);
max[a[1]] = Math.max(v1, v2);
}

System.out.println(max[T]);
}

private int getMax(int[] max, int t) {
for (int i=t; i>=0; i--) {
if (max[i] > 0) return max[i];
}
return 0;
}

g*02012-09-24 07:09

9 楼

Yes, true dat!

【在 d*******d 的大作中提到】

: I guess dp will do

m*q2012-09-24 07:09

10 楼

程序有点没看懂，看描述复杂度是O(n^2)?
这题应该可以O(nlgn)的

..

【在 g**********y 的大作中提到】

: 写了一个ugly的实现，想法是把presentation按结束时间排序。最后结束时间T，M[0..
: T]记录时间0..t的最大利用值。
: M[A(n,1)] = max{A(n,1)-A(n,0)+max(M[0..A(n,0)]), max(M[0..A(n,1)])}
: 程序应该可以简化，要输出选择的presentation, 数据结构也要改。
: public void maxUse(List list) {
: Collections.sort(list, new Comparator() {
: public int compare(int[] a, int[] b) {
: return a[1] - b[1];
: }
: });

i*d2012-09-24 07:09

11 楼

你这个greedy的取值条件不对。
应该是首先按照结束时间排序，然后greedy的每次取最早结束的presentation.
并且remove有overlap的presentation
按照这个例子应该首先排序成
[0,2],[3,7],[3,12],[8,15],[14,15]
首先取 [0,2]
然后取 [3,7] 并remove有overlap的[3,12]
最后取 [8,15], 并remove掉[14,15]
结果就是[0,2],[3,7],[8,15]

【在 s*****y 的大作中提到】

: [0,2] [3,12][14,15] [3,7][8,15]
: greedy will be [0,2] [3,12][14,15]
: but best should be [0,2][3,7][8,15]