这个$350, 6寸的手机秒杀 1+2, 相机估计可以与 iphone 6s 比肩 - 未名空间MITBBS历史存档

这个$350, 6寸的手机秒杀 1+2, 相机估计可以与 iphone 6s 比肩# PDA - 掌中宝

p*92015-10-21 07:10

1 楼

今天看到一道Google的面试题，想了半天不知道自己的解法对不对，上来跟大家讨论一
下。
题目是装载问题的变种：要把n个箱子装到m个船上，每个箱子的重量是Wi, 每个船的载
重是Cj，问怎么样装才能把这m个船尽可能装满？即所有船的剩余空间之和最小。
不知用DP这样做对不对：opt(i, j)表示剩余载重空间为j时装载第i个箱子所能得到的
最小剩余空间，递归公式为：
opt(i, j) = min(opt(i-1,j), opt(i-1,j+k)-k). 其中k表示第i个货物分别装到m个船
上时所剩余的总载重空间。
不知这样做对不对，有没有更简单的解法？谢谢！

m*i2015-10-21 07:10

2 楼

不知上哪去问，客服下班了，只好上娘家版来问了。

s*e2015-10-21 07:10

3 楼

blu pure xl, 据称是金立e8 的孪生兄弟。金立e8 在国内卖到坑爹的3999，这个blu一
模一样的规格却只有$350 （amazon的报价）, 如果硬件没有打折的话，那么性价比是
相当不错的。相机 24M, 还有 ois, 就是cpu MTK Helio X10 弱了些，稍重了些，规
格无论从哪方面都秒杀 1+2。
买个手机居然还要邀请信，真是奇葩。

g*a2015-10-21 07:10

4 楼

用DP,matrix(i,j)表示第j条船上在放第i个箱子时候的载重。matrix(i,j)=Wi+matrix(
i-1,j). j 从0到m，包括不放在任何一条船上的情况。放完一个箱子，如果matrix(i,j
)>Cj for every j, 记录这时候的剩余空间。比较最后输出最小值。

Y*02015-10-21 07:10

5 楼

可以改,但不可改出发城市.
打中文客服
Mandarin Chinese
1-800-492-8095

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

: 不知上哪去问，客服下班了，只好上娘家版来问了。

s*y2015-10-21 07:10

6 楼

别的不说，造型做工完败于Oneplus2.

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

: blu pure xl, 据称是金立e8 的孪生兄弟。金立e8 在国内卖到坑爹的3999，这个blu一
: 模一样的规格却只有$350 （amazon的报价）, 如果硬件没有打折的话，那么性价比是
: 相当不错的。相机 24M, 还有 ois, 就是cpu MTK Helio X10 弱了些，稍重了些，规
: 格无论从哪方面都秒杀 1+2。
: 买个手机居然还要邀请信，真是奇葩。

g*a2015-10-21 07:10

7 楼

貌似sort箱子重量后会更快一点

m*i2015-10-21 07:10

8 楼

谢谢

u*d2015-10-21 07:10

9 楼

看了看，除了个大体沉，没啥亮点。cpu，内存，频段支持，电池是短板，相机参数没
见OIS，也没有测评，无法判断好坏。

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

: blu pure xl, 据称是金立e8 的孪生兄弟。金立e8 在国内卖到坑爹的3999，这个blu一
: 模一样的规格却只有$350 （amazon的报价）, 如果硬件没有打折的话，那么性价比是
: 相当不错的。相机 24M, 还有 ois, 就是cpu MTK Helio X10 弱了些，稍重了些，规
: 格无论从哪方面都秒杀 1+2。
: 买个手机居然还要邀请信，真是奇葩。

P*L2015-10-21 07:10

10 楼

题目叙述有误，所有船的剩余空间之和是一个定值 ΣCj - ΣWi

【在 p*****9 的大作中提到】

: 今天看到一道Google的面试题，想了半天不知道自己的解法对不对，上来跟大家讨论一
: 下。
: 题目是装载问题的变种：要把n个箱子装到m个船上，每个箱子的重量是Wi, 每个船的载
: 重是Cj，问怎么样装才能把这m个船尽可能装满？即所有船的剩余空间之和最小。
: 不知用DP这样做对不对：opt(i, j)表示剩余载重空间为j时装载第i个箱子所能得到的
: 最小剩余空间，递归公式为：
: opt(i, j) = min(opt(i-1,j), opt(i-1,j+k)-k). 其中k表示第i个货物分别装到m个船
: 上时所剩余的总载重空间。
: 不知这样做对不对，有没有更简单的解法？谢谢！

h*b2015-10-21 07:10

11 楼

350左右的价格，随便买一个都比这个好吧，lg g4，n6

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

: blu pure xl, 据称是金立e8 的孪生兄弟。金立e8 在国内卖到坑爹的3999，这个blu一
: 模一样的规格却只有$350 （amazon的报价）, 如果硬件没有打折的话，那么性价比是
: 相当不错的。相机 24M, 还有 ois, 就是cpu MTK Helio X10 弱了些，稍重了些，规
: 格无论从哪方面都秒杀 1+2。
: 买个手机居然还要邀请信，真是奇葩。

g*a2015-10-21 07:10

12 楼

我猜应该是n个箱子不一定全部要放上去，能放多少放多少，哪样剩的空间最小

【在 P*******L 的大作中提到】

: 题目叙述有误，所有船的剩余空间之和是一个定值 ΣCj - ΣWi

s*e2015-10-21 07:10

13 楼

相机有ois, f2.0, 照相估计比不过lg g4, 应该能胜过n6, 而且这款相机有物理按键

p*92015-10-21 07:10

14 楼

sorry, 我题目没说明白。不一定所有的箱子都能装上去啊，会超重的。题目的意思是
，在每个船都不超重的情况下，尽可能装满。

【在 P*******L 的大作中提到】

: 题目叙述有误，所有船的剩余空间之和是一个定值 ΣCj - ΣWi

r*72015-10-21 07:10

15 楼

有m条船你只记一个j不够吧。
应该是opt(i, j1, j2, ..., jm) = max(max(Wi + opt(i-1, j1, j2, ..jk - Wi, ...
jm)), opt(i - 1, j1, j2...jm))

【在 p*****9 的大作中提到】

: 今天看到一道Google的面试题，想了半天不知道自己的解法对不对，上来跟大家讨论一
: 下。
: 题目是装载问题的变种：要把n个箱子装到m个船上，每个箱子的重量是Wi, 每个船的载
: 重是Cj，问怎么样装才能把这m个船尽可能装满？即所有船的剩余空间之和最小。
: 不知用DP这样做对不对：opt(i, j)表示剩余载重空间为j时装载第i个箱子所能得到的
: 最小剩余空间，递归公式为：
: opt(i, j) = min(opt(i-1,j), opt(i-1,j+k)-k). 其中k表示第i个货物分别装到m个船
: 上时所剩余的总载重空间。
: 不知这样做对不对，有没有更简单的解法？谢谢！

p*92015-10-21 07:10

16 楼

嗯，有道理。。。我靠，好复杂……

..

【在 r****7 的大作中提到】

: 有m条船你只记一个j不够吧。
: 应该是opt(i, j1, j2, ..., jm) = max(max(Wi + opt(i-1, j1, j2, ..jk - Wi, ...
: jm)), opt(i - 1, j1, j2...jm))

t*l2015-10-21 07:10

17 楼

maximum flow problem

【在 p*****9 的大作中提到】

: 今天看到一道Google的面试题，想了半天不知道自己的解法对不对，上来跟大家讨论一
: 下。
: 题目是装载问题的变种：要把n个箱子装到m个船上，每个箱子的重量是Wi, 每个船的载
: 重是Cj，问怎么样装才能把这m个船尽可能装满？即所有船的剩余空间之和最小。
: 不知用DP这样做对不对：opt(i, j)表示剩余载重空间为j时装载第i个箱子所能得到的
: 最小剩余空间，递归公式为：
: opt(i, j) = min(opt(i-1,j), opt(i-1,j+k)-k). 其中k表示第i个货物分别装到m个船
: 上时所剩余的总载重空间。
: 不知这样做对不对，有没有更简单的解法？谢谢！

d*12015-10-21 07:10

18 楼

第一眼感觉是线性优化的题目。
用 simplex method。
每个Wi 重复出现m次就行。然后再给一个船，容量无限，但权重为0
-------但，这里我们得要未知数为0，1的怎么去限制----------
-----------------求大牛们拍醒----------

M*a2015-10-21 07:10

19 楼

不用几条船，如果就一条船的情况下就已经NP了，只有伪多项式算法。

a*u2015-10-21 07:10

20 楼

多背包问题近似解法及其近似比。
http://www.cnblogs.com/jiaorenyu/p/3416762.html
这应该是一道NP-Hard的问题。

l*y2015-10-21 07:10

21 楼

Brutal force DFS worst case scenario (m+1)^n 可以么

f*g2015-10-21 07:10

22 楼

如果DFS的话，复杂度是m!个knapsack problem吧

p*92015-10-21 07:10

23 楼

今天看到一道Google的面试题，想了半天不知道自己的解法对不对，上来跟大家讨论一
下。
题目是装载问题的变种：要把n个箱子装到m个船上，每个箱子的重量是Wi, 每个船的载
重是Cj，问怎么样装才能把这m个船尽可能装满？即所有船的剩余空间之和最小。
不知用DP这样做对不对：opt(i, j)表示剩余载重空间为j时装载第i个箱子所能得到的
最小剩余空间，递归公式为：
opt(i, j) = min(opt(i-1,j), opt(i-1,j+k)-k). 其中k表示第i个货物分别装到m个船
上时所剩余的总载重空间。
不知这样做对不对，有没有更简单的解法？谢谢！

g*a2015-10-21 07:10

24 楼

用DP,matrix(i,j)表示第j条船上在放第i个箱子时候的载重。matrix(i,j)=Wi+matrix(
i-1,j). j 从0到m，包括不放在任何一条船上的情况。放完一个箱子，如果matrix(i,j
)>Cj for every j, 记录这时候的剩余空间。比较最后输出最小值。

g*a2015-10-21 07:10

25 楼

貌似sort箱子重量后会更快一点

P*L2015-10-21 07:10

26 楼

题目叙述有误，所有船的剩余空间之和是一个定值 ΣCj - ΣWi

【在 p*****9 的大作中提到】

: 今天看到一道Google的面试题，想了半天不知道自己的解法对不对，上来跟大家讨论一
: 下。
: 题目是装载问题的变种：要把n个箱子装到m个船上，每个箱子的重量是Wi, 每个船的载
: 重是Cj，问怎么样装才能把这m个船尽可能装满？即所有船的剩余空间之和最小。
: 不知用DP这样做对不对：opt(i, j)表示剩余载重空间为j时装载第i个箱子所能得到的
: 最小剩余空间，递归公式为：
: opt(i, j) = min(opt(i-1,j), opt(i-1,j+k)-k). 其中k表示第i个货物分别装到m个船
: 上时所剩余的总载重空间。
: 不知这样做对不对，有没有更简单的解法？谢谢！

g*a2015-10-21 07:10

27 楼

我猜应该是n个箱子不一定全部要放上去，能放多少放多少，哪样剩的空间最小

【在 P*******L 的大作中提到】

: 题目叙述有误，所有船的剩余空间之和是一个定值 ΣCj - ΣWi

p*92015-10-21 07:10

28 楼

sorry, 我题目没说明白。不一定所有的箱子都能装上去啊，会超重的。题目的意思是
，在每个船都不超重的情况下，尽可能装满。

【在 P*******L 的大作中提到】

: 题目叙述有误，所有船的剩余空间之和是一个定值 ΣCj - ΣWi

r*72015-10-21 07:10

29 楼

有m条船你只记一个j不够吧。
应该是opt(i, j1, j2, ..., jm) = max(max(Wi + opt(i-1, j1, j2, ..jk - Wi, ...
jm)), opt(i - 1, j1, j2...jm))

【在 p*****9 的大作中提到】

: 今天看到一道Google的面试题，想了半天不知道自己的解法对不对，上来跟大家讨论一
: 下。
: 题目是装载问题的变种：要把n个箱子装到m个船上，每个箱子的重量是Wi, 每个船的载
: 重是Cj，问怎么样装才能把这m个船尽可能装满？即所有船的剩余空间之和最小。
: 不知用DP这样做对不对：opt(i, j)表示剩余载重空间为j时装载第i个箱子所能得到的
: 最小剩余空间，递归公式为：
: opt(i, j) = min(opt(i-1,j), opt(i-1,j+k)-k). 其中k表示第i个货物分别装到m个船
: 上时所剩余的总载重空间。
: 不知这样做对不对，有没有更简单的解法？谢谢！

p*92015-10-21 07:10

30 楼

嗯，有道理。。。我靠，好复杂……

..

【在 r****7 的大作中提到】

: 有m条船你只记一个j不够吧。
: 应该是opt(i, j1, j2, ..., jm) = max(max(Wi + opt(i-1, j1, j2, ..jk - Wi, ...
: jm)), opt(i - 1, j1, j2...jm))

t*l2015-10-21 07:10

31 楼

maximum flow problem

【在 p*****9 的大作中提到】

: 今天看到一道Google的面试题，想了半天不知道自己的解法对不对，上来跟大家讨论一
: 下。
: 题目是装载问题的变种：要把n个箱子装到m个船上，每个箱子的重量是Wi, 每个船的载
: 重是Cj，问怎么样装才能把这m个船尽可能装满？即所有船的剩余空间之和最小。
: 不知用DP这样做对不对：opt(i, j)表示剩余载重空间为j时装载第i个箱子所能得到的
: 最小剩余空间，递归公式为：
: opt(i, j) = min(opt(i-1,j), opt(i-1,j+k)-k). 其中k表示第i个货物分别装到m个船
: 上时所剩余的总载重空间。
: 不知这样做对不对，有没有更简单的解法？谢谢！

d*12015-10-21 07:10

32 楼

第一眼感觉是线性优化的题目。
用 simplex method。
每个Wi 重复出现m次就行。然后再给一个船，容量无限，但权重为0
-------但，这里我们得要未知数为0，1的怎么去限制----------
-----------------求大牛们拍醒----------

M*a2015-10-21 07:10

33 楼

不用几条船，如果就一条船的情况下就已经NP了，只有伪多项式算法。

a*u2015-10-21 07:10

34 楼

多背包问题近似解法及其近似比。
http://www.cnblogs.com/jiaorenyu/p/3416762.html
这应该是一道NP-Hard的问题。

l*y2015-10-21 07:10

35 楼

Brutal force DFS worst case scenario (m+1)^n 可以么

f*g2015-10-21 07:10

36 楼

如果DFS的话，复杂度是m!个knapsack problem吧

c*n2015-10-21 07:10

37 楼

这道题确实很变态, multiple knapsack problem。今天刷topcoder 遇到一个类似问题
。可以学习一下。
http://community.topcoder.com/tc?module=Static&d1=match_editori
题目叫collectingmarbles.
需要保持的状态非常多。

s*x2015-10-21 07:10

38 楼

G家确实很变态