问个搬家搬花的问题，班班手下留情 - 未名空间MITBBS历史存档

问个搬家搬花的问题，班班手下留情# gardening - 拈花惹草

x*n2013-10-22 07:10

1 楼

这个切肉机我用了快十年了，很好用，羊肉冻一下，可以切的薄薄的自然卷。
另外这个切肉机自带的是serrated blade，要切的很薄需要练练，有一点点技巧。左手
控制厚薄的按钮要随时根据肉的情况调整，肉碰到刀片的一刻就决定了这片肉切的好不
好。
amazon有卖配套的non-serrated blade，non-serrated blade才是真正设计用来切很薄
片的，配610那真是切羊肉片的神器！强烈推荐！
Chefs Choice Blade for 610 Non Serrated - Ultra Thin Slicers：
http://www.amazon.com/gp/product/B000X1EOTO/

f*i2013-10-22 07:10

2 楼

given is an unsorted integer array, how to divide it into two subarrays,
such that the averages of these two arrays are the same (or have minimum
difference).
what if those are positive integers only, and what happens when it is mixed
with positive and negative integers?

a*d2013-10-22 07:10

3 楼

double ordered
ask for 60.00 obo
amazon price: 89.00
very useful in la area to avoid cops
in west la, can bring to the east la area
in its original package, brand new
for technical specs, pls see
http://www.amazon.com/Cobra-XRS-9730-12-Band-Radar-Detector/dp/B000ECO50U
thx

m*i2013-10-22 07:10

4 楼

要跨洲搬家，搬家公司给搬植物吗？

f*82013-10-22 07:10

5 楼

注意下，冬天要入一台了～

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

: 这个切肉机我用了快十年了，很好用，羊肉冻一下，可以切的薄薄的自然卷。
: 另外这个切肉机自带的是serrated blade，要切的很薄需要练练，有一点点技巧。左手
: 控制厚薄的按钮要随时根据肉的情况调整，肉碰到刀片的一刻就决定了这片肉切的好不
: 好。
: amazon有卖配套的non-serrated blade，non-serrated blade才是真正设计用来切很薄
: 片的，配610那真是切羊肉片的神器！强烈推荐！
: Chefs Choice Blade for 610 Non Serrated - Ultra Thin Slicers：
: http://www.amazon.com/gp/product/B000X1EOTO/

g*k2013-10-22 07:10

6 楼

如果不需要重新排序而且都是正数的话，先scan求总和，
for (i = n; i>0; --n)
比较 sum(A[1..i])/i 和 sum(A[i+1..n])/(n-i)
如果当前差值比前次要大，直接返回i+1
如果有负数的话，那么就得老老实实从后往前找最小差值。
如果题目的意思是要重新排列数组，并且划分成两组的话，就没有什么思路了。

mixed

【在 f*********i 的大作中提到】

: given is an unsorted integer array, how to divide it into two subarrays,
: such that the averages of these two arrays are the same (or have minimum
: difference).
: what if those are positive integers only, and what happens when it is mixed
: with positive and negative integers?

T*m2013-10-22 07:10

7 楼

要看搬家公司，干不死的应该可以的吧。

【在 m**i 的大作中提到】

: 要跨洲搬家，搬家公司给搬植物吗？

B*n2013-10-22 07:10

8 楼

mark

h*n2013-10-22 07:10

9 楼

s/he said subarray, so I guess s/he meant your way?

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

: 如果不需要重新排序而且都是正数的话，先scan求总和，
: for (i = n; i>0; --n)
: 比较 sum(A[1..i])/i 和 sum(A[i+1..n])/(n-i)
: 如果当前差值比前次要大，直接返回i+1
: 如果有负数的话，那么就得老老实实从后往前找最小差值。
: 如果题目的意思是要重新排列数组，并且划分成两组的话，就没有什么思路了。
:
: mixed

C*G2013-10-22 07:10

10 楼

活的不行，你要问你的搬家公司

l*s2013-10-22 07:10

11 楼

和662，667 比起来有啥不一样

g*k2013-10-22 07:10

12 楼

if there are negative numbers, does this work?
pick a random pivot then put it to the right position,
calculate mean for left and right subarray, if left > right, pick another
pivot in the left subarray, if left < right, pick another pivot in the right
subarray, until it is equal or return the smaller difference one.
and it seems my previous post doesn't work for all positive numbers neither.
I can't prove its correctness and find a couter example.
Hope some big cow chips in

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

: s/he said subarray, so I guess s/he meant your way?

m*i2013-10-22 07:10

13 楼

55555我的花花们咋办呀，辛辛苦苦攒下的兰花，茉莉，还有玫瑰，心痛呀

s*i2013-10-22 07:10

14 楼

到底啥技巧啊。。。。
那个刀片够贵的。。。。

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

: 这个切肉机我用了快十年了，很好用，羊肉冻一下，可以切的薄薄的自然卷。
: 另外这个切肉机自带的是serrated blade，要切的很薄需要练练，有一点点技巧。左手
: 控制厚薄的按钮要随时根据肉的情况调整，肉碰到刀片的一刻就决定了这片肉切的好不
: 好。
: amazon有卖配套的non-serrated blade，non-serrated blade才是真正设计用来切很薄
: 片的，配610那真是切羊肉片的神器！强烈推荐！
: Chefs Choice Blade for 610 Non Serrated - Ultra Thin Slicers：
: http://www.amazon.com/gp/product/B000X1EOTO/

g*y2013-10-22 07:10

15 楼

http://people.csail.mit.edu/bdean/6.046/dp/
如果这个数组是有界的，比如最大K, DP可以解。如上。
如果不知道界，这是NP problem, 就不要费心琢磨了。

T*m2013-10-22 07:10

16 楼

自己开车带啊！

【在 m**i 的大作中提到】

: 55555我的花花们咋办呀，辛辛苦苦攒下的兰花，茉莉，还有玫瑰，心痛呀

K*n2013-10-22 07:10

17 楼

mark

g*02013-10-22 07:10

18 楼

为什么有negative numbers, 要从后往前找最小差值？
可不可以给个example?
xiexie

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

: 如果不需要重新排序而且都是正数的话，先scan求总和，
: for (i = n; i>0; --n)
: 比较 sum(A[1..i])/i 和 sum(A[i+1..n])/(n-i)
: 如果当前差值比前次要大，直接返回i+1
: 如果有负数的话，那么就得老老实实从后往前找最小差值。
: 如果题目的意思是要重新排列数组，并且划分成两组的话，就没有什么思路了。
:
: mixed

x*22013-10-22 07:10

19 楼

弄好防水措施，应该可以的。比如，把几盆几盆的花分别放在大盆里或大蓝子里，有的
用塑料袋把盆给包起来。搬家公司一般不会拒绝的，但他们会计算收费的。

r*y2013-10-22 07:10

20 楼

擦，刀片涨到$30块了，后悔$20的时候没买

g*02013-10-22 07:10

21 楼

sorry, never mind. Got it. :P

y*82013-10-22 07:10

22 楼

在路上要走几天？天数短肯定可以成功活搬啊。pack是个技术活。

要跨洲搬家，搬家公司给搬植物吗？

【在 m**i 的大作中提到】

: 要跨洲搬家，搬家公司给搬植物吗？

s*d2013-10-22 07:10

23 楼

刚入机器，正好看到推荐刀片，非常感谢！

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

: 这个切肉机我用了快十年了，很好用，羊肉冻一下，可以切的薄薄的自然卷。
: 另外这个切肉机自带的是serrated blade，要切的很薄需要练练，有一点点技巧。左手
: 控制厚薄的按钮要随时根据肉的情况调整，肉碰到刀片的一刻就决定了这片肉切的好不
: 好。
: amazon有卖配套的non-serrated blade，non-serrated blade才是真正设计用来切很薄
: 片的，配610那真是切羊肉片的神器！强烈推荐！
: Chefs Choice Blade for 610 Non Serrated - Ultra Thin Slicers：
: http://www.amazon.com/gp/product/B000X1EOTO/

g*s2013-10-22 07:10

24 楼

这题是求平均，更难。求和可以用DP，平均好像不行。

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

: http://people.csail.mit.edu/bdean/6.046/dp/
: 如果这个数组是有界的，比如最大K, DP可以解。如上。
: 如果不知道界，这是NP problem, 就不要费心琢磨了。

T*42013-10-22 07:10

25 楼

嗯，耐旱的植物，自己先包好了，放箱子里，和其他物品一起走应该可以。
或者自己开车带上不好包起来的

【在 x******2 的大作中提到】

: 弄好防水措施，应该可以的。比如，把几盆几盆的花分别放在大盆里或大蓝子里，有的
: 用塑料袋把盆给包起来。搬家公司一般不会拒绝的，但他们会计算收费的。

m*d2013-10-22 07:10

26 楼

技巧就是保持肉的切面角度稳定和挤压力道恒定

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

: 到底啥技巧啊。。。。
: 那个刀片够贵的。。。。

g*s2013-10-22 07:10

27 楼

函数不单调，这个方法不对。
不过，如果是这个理解的话，全算一遍也是O(n）啊。
难的是subset

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

: 如果不需要重新排序而且都是正数的话，先scan求总和，
: for (i = n; i>0; --n)
: 比较 sum(A[1..i])/i 和 sum(A[i+1..n])/(n-i)
: 如果当前差值比前次要大，直接返回i+1
: 如果有负数的话，那么就得老老实实从后往前找最小差值。
: 如果题目的意思是要重新排列数组，并且划分成两组的话，就没有什么思路了。
:
: mixed

m*i2013-10-22 07:10

28 楼

太远了，开不了。

【在 T*******m 的大作中提到】

: 自己开车带啊！

v*a2013-10-22 07:10

29 楼

mark

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

: 这个切肉机我用了快十年了，很好用，羊肉冻一下，可以切的薄薄的自然卷。
: 另外这个切肉机自带的是serrated blade，要切的很薄需要练练，有一点点技巧。左手
: 控制厚薄的按钮要随时根据肉的情况调整，肉碰到刀片的一刻就决定了这片肉切的好不
: 好。
: amazon有卖配套的non-serrated blade，non-serrated blade才是真正设计用来切很薄
: 片的，配610那真是切羊肉片的神器！强烈推荐！
: Chefs Choice Blade for 610 Non Serrated - Ultra Thin Slicers：
: http://www.amazon.com/gp/product/B000X1EOTO/

g*e2013-10-22 07:10

30 楼

这题到底能不能移动数组里的元素？如果不能移动，那就很简单了，一共也就n种分法
如果可以移动，是NP了

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

: 这题是求平均，更难。求和可以用DP，平均好像不行。

m*i2013-10-22 07:10

31 楼

电话问了，不给搬活的植物，连油，洗衣液，漂白剂都不给搬。

【在 x******2 的大作中提到】

: 弄好防水措施，应该可以的。比如，把几盆几盆的花分别放在大盆里或大蓝子里，有的
: 用塑料袋把盆给包起来。搬家公司一般不会拒绝的，但他们会计算收费的。

t*g2013-10-22 07:10

32 楼

黑五这东西有deal么

g*k2013-10-22 07:10

33 楼

是啊。可是题目里要区分全正和有负数的情况，看来还是有什么地方没有考虑到。
不知道什么情况下能够直接判断已得最优解。

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

: 函数不单调，这个方法不对。
: 不过，如果是这个理解的话，全算一遍也是O(n）啊。
: 难的是subset

l*s2013-10-22 07:10

34 楼

也正考虑进一个类似的刨肉

g*s2013-10-22 07:10

35 楼

我的意思是应该是subset.否则太简单了。

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

: 是啊。可是题目里要区分全正和有负数的情况，看来还是有什么地方没有考虑到。
: 不知道什么情况下能够直接判断已得最优解。

l*s2013-10-22 07:10

36 楼

功率大的这个机子能切带骨头吗

g*k2013-10-22 07:10

37 楼

如果允许负数，应该是指对数没有限制吧，没有限制的话，subset就是指数级的啦。

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

: 我的意思是应该是subset.否则太简单了。

l*32013-10-22 07:10

38 楼

应该不能，我用７千的商用切片机有大些的骨头一样卡住

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

: 功率大的这个机子能切带骨头吗

f*i2013-10-22 07:10

39 楼

不好意思,是我没有把题目说清楚.
是把这个array里面的integer分到两个subsets里面,所以貌似一个NP问题.
我觉得关键是在如何减枝操作,如果都是positive的话,应该可以用DP来做把,维护两个
subsets,然后不断添加.
或者,divide and conquer, 如果有类似a1+a2=a3+a4,那么这四个数就自动归类到两个
subsets中,这样可以减少比较次数,当然,要考虑a1+a3=a2+a4,或者其他combination的
情况.
没有头绪....

t*g2013-10-22 07:10

40 楼

610好像断产了，609还有很多地方有卖，这两个型号有区别么？

g*k2013-10-22 07:10

41 楼

如果是求average的话，没有必要考虑正负，
求出最小数，如果是-x, 那么所有的数你都+x，这样数组就都是正数了，而且不影响结
果。
你不妨给出DP的解法来看看?

【在 f*********i 的大作中提到】

: 不好意思,是我没有把题目说清楚.
: 是把这个array里面的integer分到两个subsets里面,所以貌似一个NP问题.
: 我觉得关键是在如何减枝操作,如果都是positive的话,应该可以用DP来做把,维护两个
: subsets,然后不断添加.
: 或者,divide and conquer, 如果有类似a1+a2=a3+a4,那么这四个数就自动归类到两个
: subsets中,这样可以减少比较次数,当然,要考虑a1+a3=a2+a4,或者其他combination的
: 情况.
: 没有头绪....

l*32013-10-22 07:10

42 楼

Mark

g*k2013-10-22 07:10

43 楼

不觉得a1+a2=a3+a4就能保证这4个数分在两个subsets中。

【在 f*********i 的大作中提到】

: 不好意思,是我没有把题目说清楚.
: 是把这个array里面的integer分到两个subsets里面,所以貌似一个NP问题.
: 我觉得关键是在如何减枝操作,如果都是positive的话,应该可以用DP来做把,维护两个
: subsets,然后不断添加.
: 或者,divide and conquer, 如果有类似a1+a2=a3+a4,那么这四个数就自动归类到两个
: subsets中,这样可以减少比较次数,当然,要考虑a1+a3=a2+a4,或者其他combination的
: 情况.
: 没有头绪....

l*s2013-10-22 07:10

44 楼

615 功率大些，塑料件少些
价格20%后几乎一样

g*y2013-10-22 07:10

45 楼

想了一下，这个还是可以用DP解, 复杂度是O(K*n^2)
a是输入数组
n = a.length
K = sum(a)
A = average(a)
S = new boolean[n][K][n] (第一维是subset最大可用的数范围，第二维是subset和，
第三维是subset size)
S[0][0][0] = true;
for i=1 to n {
for j=1 to K {
for k=1 to n {
S[i][j][k] = S[i-1][j][k] || (j>a[i] && S[i-1][j-a[i]][k-1]);
}
}
}
best = Integer.MAX_VALUE
for i=1 to n {
avg = A * i;
find t closest to avg that S[n][t][i] = true;
if |t/i - avg| < |best - avg| then best = t/i;
}
return best;

h*02013-10-22 07:10

46 楼

什么是“价格20%”？介绍一下有什么折扣。

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

: 615 功率大些，塑料件少些
: 价格20%后几乎一样

d*l2013-10-22 07:10

47 楼

我觉得这个做法正确性应该是没问题的，相当于是背包问题的一个变化。不过背包问题
本身就是NP问题，上面说的也没错。
程序有点小问题，第二维是subset的和的话，开max(a)是不够的，应该是想写sum(a)吧
？不过这个方法简单易行，真要是面试的时候就它了

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

: 想了一下，这个还是可以用DP解, 复杂度是O(K*n^2)
: a是输入数组
: n = a.length
: K = sum(a)
: A = average(a)
: S = new boolean[n][K][n] (第一维是subset最大可用的数范围，第二维是subset和，
: 第三维是subset size)
: S[0][0][0] = true;
: for i=1 to n {
: for j=1 to K {

l*s2013-10-22 07:10

48 楼

20% OFF coupon

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

: 什么是“价格20%”？介绍一下有什么折扣。

g*y2013-10-22 07:10

49 楼

对，是sum(a).
这个问题对于普遍情况，肯定是NPC。面试问的话，应该是这种有界的。

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

: 我觉得这个做法正确性应该是没问题的，相当于是背包问题的一个变化。不过背包问题
: 本身就是NP问题，上面说的也没错。
: 程序有点小问题，第二维是subset的和的话，开max(a)是不够的，应该是想写sum(a)吧
: ？不过这个方法简单易行，真要是面试的时候就它了

l*s2013-10-22 07:10

50 楼

20%off coupon

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

: 什么是“价格20%”？介绍一下有什么折扣。

g*s2013-10-22 07:10

51 楼

The idea is correct but the last step has error.
for i=1 to n {
avg = A * i;
find t closest to avg that S[n][t][i] = true;
if |t/i - avg| < |best - avg| then best = t/i;
}
then it would always divide to two group with size n and 0 since t/n-
avg=0 when t=sumOf(a);
even if using for i=1 to n-1, it is still not correct:e.g.
1,4,4,8,8 avg=5
by this way, you will divide to {1 4 8 8} and {4} but correct one should
be {1 8} { 4 4 8}
should change to:
for i=1 to n {
avg1 = t/i;
avg2 = (sum-t) / (n-i)
//find t let avg1 avg2 is closest while S[n][t][i] = true;
if abs(avg1-avg2) < best then best = t/i;
}

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

: 想了一下，这个还是可以用DP解, 复杂度是O(K*n^2)
: a是输入数组
: n = a.length
: K = sum(a)
: A = average(a)
: S = new boolean[n][K][n] (第一维是subset最大可用的数范围，第二维是subset和，
: 第三维是subset size)
: S[0][0][0] = true;
: for i=1 to n {
: for j=1 to K {

l*s2013-10-22 07:10

52 楼

嗯，那就了心事了
谢啦

【在 l**********3 的大作中提到】

: 应该不能，我用７千的商用切片机有大些的骨头一样卡住

g*e2013-10-22 07:10

53 楼

先顶再看

和，

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

: The idea is correct but the last step has error.
: for i=1 to n {
: avg = A * i;
: find t closest to avg that S[n][t][i] = true;
: if |t/i - avg| < |best - avg| then best = t/i;
: }
: then it would always divide to two group with size n and 0 since t/n-
: avg=0 when t=sumOf(a);
: even if using for i=1 to n-1, it is still not correct:e.g.
: 1,4,4,8,8 avg=5

y*c2013-10-22 07:10

54 楼

买了一个月就坏了，幸好早坏，还能退

g*y2013-10-22 07:10

55 楼

对，应该是for i=1 to n-1
但是你举的例子不对，S[n][K][n]算的是可以用1..n的元素，可以生成的所有和，用的
元素的个数。所以最后的循环是用的元素的个数，不是可以用的元素。

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

: The idea is correct but the last step has error.
: for i=1 to n {
: avg = A * i;
: find t closest to avg that S[n][t][i] = true;
: if |t/i - avg| < |best - avg| then best = t/i;
: }
: then it would always divide to two group with size n and 0 since t/n-
: avg=0 when t=sumOf(a);
: even if using for i=1 to n-1, it is still not correct:e.g.
: 1,4,4,8,8 avg=5

s*d2013-10-22 07:10

56 楼

上来汇报一下，610+刀片非常完美，再次感谢分享！

g*s2013-10-22 07:10

57 楼

the sample:
1 4 4 8 8
avg = 5
the best by your step will get best=0.25 -- (t = 21, i = 4, t/i-avg=0.25)
which is: {1 4 8 8} and {4}.
{1 4 8 8} {4} the |avg1 - avg2| = 1.25
correct one should be:
{1 8} { 4 4 8} the |avg1 - avg2| = 0.83

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

: 对，应该是for i=1 to n-1
: 但是你举的例子不对，S[n][K][n]算的是可以用1..n的元素，可以生成的所有和，用的
: 元素的个数。所以最后的循环是用的元素的个数，不是可以用的元素。

a*g2013-10-22 07:10

58 楼

good

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

: 这个切肉机我用了快十年了，很好用，羊肉冻一下，可以切的薄薄的自然卷。
: 另外这个切肉机自带的是serrated blade，要切的很薄需要练练，有一点点技巧。左手
: 控制厚薄的按钮要随时根据肉的情况调整，肉碰到刀片的一刻就决定了这片肉切的好不
: 好。
: amazon有卖配套的non-serrated blade，non-serrated blade才是真正设计用来切很薄
: 片的，配610那真是切羊肉片的神器！强烈推荐！
: Chefs Choice Blade for 610 Non Serrated - Ultra Thin Slicers：
: http://www.amazon.com/gp/product/B000X1EOTO/

d*l2013-10-22 07:10

59 楼

这题第一步出来第二步就是trivial的了，最差K*n次把所有可能的情况都比一遍，也不
影响总体复杂度。似乎也有些更巧的办法，但是正确性稍有点不好确定。

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

: 对，应该是for i=1 to n-1
: 但是你举的例子不对，S[n][K][n]算的是可以用1..n的元素，可以生成的所有和，用的
: 元素的个数。所以最后的循环是用的元素的个数，不是可以用的元素。

g*y2013-10-22 07:10

60 楼

以你的例子，
avg = 5
用1个数可以生成的：1, 4, 4, 8, 8
所以最佳解是用{4}, {1, 4, 8, 8}, best=4
用2个数可以生成的：5， 8， 9， 12， 16
所以最佳解是用{1,8}, {1,4,8}, t=4.5, so best = 4.5
用3个数以上可以生成的，和以上情况互补，所以不用再算了。
写这个时候，才注意到算到n/2就行了。算小优化吧。

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

: the sample:
: 1 4 4 8 8
: avg = 5
: the best by your step will get best=0.25 -- (t = 21, i = 4, t/i-avg=0.25)
: which is: {1 4 8 8} and {4}.
: {1 4 8 8} {4} the |avg1 - avg2| = 1.25
: correct one should be:
: {1 8} { 4 4 8} the |avg1 - avg2| = 0.83

g*s2013-10-22 07:10

61 楼

I agree. The DP is part is correct.

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

: 这题第一步出来第二步就是trivial的了，最差K*n次把所有可能的情况都比一遍，也不
: 影响总体复杂度。似乎也有些更巧的办法，但是正确性稍有点不好确定。

g*s2013-10-22 07:10

62 楼

no. then 4个数,
(1,4,8,8), t=5.25, so best =0.25

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

: 以你的例子，
: avg = 5
: 用1个数可以生成的：1, 4, 4, 8, 8
: 所以最佳解是用{4}, {1, 4, 8, 8}, best=4
: 用2个数可以生成的：5， 8， 9， 12， 16
: 所以最佳解是用{1,8}, {1,4,8}, t=4.5, so best = 4.5
: 用3个数以上可以生成的，和以上情况互补，所以不用再算了。
: 写这个时候，才注意到算到n/2就行了。算小优化吧。

g*y2013-10-22 07:10

63 楼

嗯，你说得对，这点我忽视了，找到最接近点之后，应该比两个subset average差值，
不是比avg(subset)-avg

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

: no. then 4个数,
: (1,4,8,8), t=5.25, so best =0.25