b*******s
发帖数: 5216 | 1 有一堆包裹，数量一定但未知，每个包裹的重量可能一样，也可能不一样。有两部小车
，设计个算法，使得两辆小车里面的包裹重量尽可能相等。 |
l*****a
发帖数: 14598 | 2 数组分两半，使差值最小
好像几周前刚讨论过
【在 b*******s 的大作中提到】
: 有一堆包裹，数量一定但未知，每个包裹的重量可能一样，也可能不一样。有两部小车
: ，设计个算法，使得两辆小车里面的包裹重量尽可能相等。
|
p*****2
发帖数: 21240 | 3
大牛帖帖你的解法，学习一下。
【在 l*****a 的大作中提到】
: 数组分两半，使差值最小
: 好像几周前刚讨论过
|
b*****x
发帖数: 48 | |
b***m
发帖数: 5987 | 5
包裹数量未知，咋整？看来是要找一个流水线策略。
【在 l*****a 的大作中提到】
: 数组分两半，使差值最小
: 好像几周前刚讨论过
|
b***m
发帖数: 5987 | 6 如果包裹数量未知，但是拿到每个包裹的时候重量可知，貌似只能是哪边轻往哪边扔了
？ |
l*****a
发帖数: 14598 | 7 这题从来没写过，不过似乎只会写成求组合，n!的复杂度，有点夸张
【在 p*****2 的大作中提到】
:
: 大牛帖帖你的解法，学习一下。
|
l*****a
发帖数: 14598 | 8 忽略了这个条件，似乎更麻烦
【在 b***m 的大作中提到】
: 如果包裹数量未知，但是拿到每个包裹的时候重量可知，貌似只能是哪边轻往哪边扔了
: ？
|
p*****2
发帖数: 21240 | 9
用两个treemap，nlogn
【在 b***m 的大作中提到】
: 如果包裹数量未知，但是拿到每个包裹的时候重量可知，貌似只能是哪边轻往哪边扔了
: ？
|
m******s
发帖数: 165 | 10 subset sum
【在 b*******s 的大作中提到】
: 有一堆包裹，数量一定但未知，每个包裹的重量可能一样，也可能不一样。有两部小车
: ，设计个算法，使得两辆小车里面的包裹重量尽可能相等。
|
|
|
w****x
发帖数: 2483 | 11
很奇怪二爷为啥还一直在job版逛？
【在 p*****2 的大作中提到】
:
: 用两个treemap，nlogn
|
l*****a
发帖数: 14598 | 12 两个heap求median?
ZKSS吧
【在 p*****2 的大作中提到】
:
: 用两个treemap，nlogn
|
p*****2
发帖数: 21240 | 13
这样可以每天都膜拜你。
【在 w****x 的大作中提到】
:
: 很奇怪二爷为啥还一直在job版逛？
|
l*****a
发帖数: 14598 | 14 二爷为啥不能够找新工作？
版上骑驴找马做题的多了，另外也许是个人业余爱好
【在 w****x 的大作中提到】
:
: 很奇怪二爷为啥还一直在job版逛？
|
p*****2
发帖数: 21240 | 15
不是heap，是treemap。
这题你不知道包裹的数量，所以要动态分配，而且需要调整。
【在 l*****a 的大作中提到】
: 两个heap求median?
: ZKSS吧
|
b***m
发帖数: 5987 | 16
Median没用吧？
【在 l*****a 的大作中提到】
: 两个heap求median?
: ZKSS吧
|
l*****a
发帖数: 14598 | 17 太难了，学习一下好猫的策略，如果面试见到，直接说不会要求换题
【在 p*****2 的大作中提到】
:
: 不是heap，是treemap。
: 这题你不知道包裹的数量，所以要动态分配，而且需要调整。
|
C***U
发帖数: 2406 | 18 O(n)近似解不知道行不行啊
这个是cpu的load balance问题吧
【在 b*******s 的大作中提到】
: 有一堆包裹，数量一定但未知，每个包裹的重量可能一样，也可能不一样。有两部小车
: ，设计个算法，使得两辆小车里面的包裹重量尽可能相等。
|
p*****2
发帖数: 21240 | 19
其实也不算难，你模拟一下
两个车装包裹，一个新的包裹过来只会发生4种情况。
假设A车和B车
1. 把新包裹放到A车
2. 把新包裹放到B车
3. 把新包裹放到A车，并且把A车的一个重量小一些的包裹放到B车，使得平衡
4. 跟3相反
你把这四种情况都算一遍，哪个结果最平衡就采用那个就可以了。
【在 l*****a 的大作中提到】
: 太难了，学习一下好猫的策略，如果面试见到，直接说不会要求换题
|
p*****2
发帖数: 21240 | 20
其实也不是爱好了。主要是我下一年的工作基本也做完了。实在是没事干了。
【在 l*****a 的大作中提到】
: 二爷为啥不能够找新工作？
: 版上骑驴找马做题的多了，另外也许是个人业余爱好
|
|
|
b***m
发帖数: 5987 | 21
这个需要允许记录所有已装车包裹的重量以及编号，关键是3、4两步怎么策略化。
【在 p*****2 的大作中提到】
:
: 其实也不是爱好了。主要是我下一年的工作基本也做完了。实在是没事干了。
|
p*****2
发帖数: 21240 | 22
Treemap，所以最后是nlogn的复杂度
【在 b***m 的大作中提到】
:
: 这个需要允许记录所有已装车包裹的重量以及编号，关键是3、4两步怎么策略化。
|
b*******s
发帖数: 5216 | 23 我表达得不清楚
包裹都已经在那里了，而且每个包裹分量都是知道的
【在 p*****2 的大作中提到】
:
: Treemap，所以最后是nlogn的复杂度
|
p*****2
发帖数: 21240 | 24
数量一定但未知
这句话什么意思？
【在 b*******s 的大作中提到】
: 我表达得不清楚
: 包裹都已经在那里了，而且每个包裹分量都是知道的
|
l*****a
发帖数: 14598 | 25 就是不知道个数？对吗
【在 b*******s 的大作中提到】
: 我表达得不清楚
: 包裹都已经在那里了，而且每个包裹分量都是知道的
|
p*****e
发帖数: 1611 | 26 经典dp,tug of war
背包的变种
【在 b*******s 的大作中提到】
: 有一堆包裹，数量一定但未知，每个包裹的重量可能一样，也可能不一样。有两部小车
: ，设计个算法，使得两辆小车里面的包裹重量尽可能相等。
|
l*****a
发帖数: 14598 | 27 那明年有head count吗？
很希望天天跟二爷学习算法，接受熏陶
【在 p*****2 的大作中提到】
:
: 数量一定但未知
: 这句话什么意思？
|
b***m
发帖数: 5987 | 28
俺treemap用得不好唉。
【在 p*****2 的大作中提到】
:
: 数量一定但未知
: 这句话什么意思？
|
b*******s
发帖数: 5216 | 29 这么牛
【在 C***U 的大作中提到】
: O(n)近似解不知道行不行啊
: 这个是cpu的load balance问题吧
|
b*******s
发帖数: 5216 | 30 忽略这个吧，我表达错了，数量一定，已知
【在 p*****2 的大作中提到】
:
: 数量一定但未知
: 这句话什么意思？
|
|
|
p*****2
发帖数: 21240 | 31
就是red black tree。你希望替换的是difference/2重量的，这样就平衡了。所以找最
接近difference/2的，这是需要logn的时间，就是binary search.
【在 b***m 的大作中提到】
:
: 俺treemap用得不好唉。
|
p*****2
发帖数: 21240 | 32
不知道能不能挨到明年呢。
【在 l*****a 的大作中提到】
: 那明年有head count吗？
: 很希望天天跟二爷学习算法，接受熏陶
|
b***m
发帖数: 5987 | 33
晕哦，题改了，不过数量未知也蛮好玩的。
【在 b*******s 的大作中提到】
: 忽略这个吧，我表达错了，数量一定，已知
|
p*****2
发帖数: 21240 | 34
那我就是2^n的算法了。上次已经被鄙视过了。DP没想明白。
【在 b*******s 的大作中提到】
: 忽略这个吧，我表达错了，数量一定，已知
|
b***m
发帖数: 5987 | 35
RBTree我学得可差了…… :-(
【在 p*****2 的大作中提到】
:
: 那我就是2^n的算法了。上次已经被鄙视过了。DP没想明白。
|
p*****2
发帖数: 21240 | 36
能不能贴个思路呢？
【在 p*****e 的大作中提到】
: 经典dp,tug of war
: 背包的变种
|
l*****a
发帖数: 14598 | 37 是你还是你们厂？
【在 p*****2 的大作中提到】
:
: 能不能贴个思路呢？
|
p*****2
发帖数: 21240 | 38
会用就行了。
【在 b***m 的大作中提到】
:
: RBTree我学得可差了…… :-(
|
p*****2
发帖数: 21240 | 39
估计我不会是最先倒下的。
【在 l*****a 的大作中提到】
: 是你还是你们厂？
|
p*****2
发帖数: 21240 | 40 跟上次的题差不多。上次是要求数量平分，这个不要求，只是要求重量相近。 |
|
|
b***m
发帖数: 5987 | 41
关键是都不会用……给稍微讲讲呗。
【在 p*****2 的大作中提到】
: 跟上次的题差不多。上次是要求数量平分，这个不要求，只是要求重量相近。
|
p*****2
发帖数: 21240 | 42
就是balanced binary search tree, 保证search的复杂度是logn
各个语言都有库类支持。Java是TreeMap, C#是SortedMap啥的吧。
【在 b***m 的大作中提到】
:
: 关键是都不会用……给稍微讲讲呗。
|
b*******s
发帖数: 5216 | 43 上次题目是最近几天的吗，找了下没找到
【在 p*****2 的大作中提到】
: 跟上次的题差不多。上次是要求数量平分，这个不要求，只是要求重量相近。
|
l*****a
发帖数: 14598 | 44 3-5周左右
当时没来得及研究
【在 b*******s 的大作中提到】
: 上次题目是最近几天的吗，找了下没找到
|
p*****e
发帖数: 1611 | 45 前面有人说了，就是subset sum，01背包问题。
如果要求数量相等，就是二维01背包。
【在 p*****2 的大作中提到】
:
: 就是balanced binary search tree, 保证search的复杂度是logn
: 各个语言都有库类支持。Java是TreeMap, C#是SortedMap啥的吧。
|
p*****2
发帖数: 21240 | 46
想了一下，如果重量都是整数，所有包裹的重量为sum的话，复杂度是N*sum。
【在 p*****e 的大作中提到】
: 前面有人说了，就是subset sum，01背包问题。
: 如果要求数量相等，就是二维01背包。
|
t****a
发帖数: 1212 | 47 这题可以用布尔线性规划来解决。
Define x \in {0, 1}, represent if the package i is selected to fill car 1.
Define variable $y=∑{x_i*w_i}-\frac{∑{w_i}}{2}$
Constraints: abs(y) < lambda, lambda > 0
Objective: minimize lambda
解法，测试数据以及结果参见http://kangtu.me/~kangtu/study/interview.html#sec-16
嗯，实际上只有5行程序来解这个问题。
【在 b*******s 的大作中提到】
: 有一堆包裹，数量一定但未知，每个包裹的重量可能一样，也可能不一样。有两部小车
: ，设计个算法，使得两辆小车里面的包裹重量尽可能相等。
|
b*******s
发帖数: 5216 | 48 明白了，多谢
【在 p*****e 的大作中提到】
: 前面有人说了，就是subset sum，01背包问题。
: 如果要求数量相等，就是二维01背包。
|
p*****2
发帖数: 21240 | 49 我写了一个dp的
static int split(int[] arr)
{
int sum=0;
for(int i : arr)
sum+=i;
int n=arr.length;
boolean[] dp=new boolean[sum/2+1];
dp[0]=true;
for(int i=0;i
{
for(int j=0;j<=sum/2-arr[i];j++)
if(dp[j])
dp[j+arr[i]]=true;
}
for(int i=sum/2;i>0;i--)
if(dp[i])
return i;
return 0;
} |
c********t
发帖数: 5706 | 50 似乎有bug
测测20,1,4
【在 p*****2 的大作中提到】
: 我写了一个dp的
: static int split(int[] arr)
: {
: int sum=0;
: for(int i : arr)
: sum+=i;
:
: int n=arr.length;
: boolean[] dp=new boolean[sum/2+1];
: dp[0]=true;
|
|
|
c********t
发帖数: 5706 | 51 最后要求是得出两车重量，还是每个包裹的分配？
【在 b*******s 的大作中提到】
: 有一堆包裹，数量一定但未知，每个包裹的重量可能一样，也可能不一样。有两部小车
: ，设计个算法，使得两辆小车里面的包裹重量尽可能相等。
|
c********t
发帖数: 5706 | 52 我觉得差一个条件，一下差得很远。
这个是一个 01背包问题 O(n*sum)
上一个无法套用背包问题，更难些，时间复杂度是O(n*n*sum)
【在 p*****2 的大作中提到】
: 跟上次的题差不多。上次是要求数量平分，这个不要求，只是要求重量相近。
|
l****o
发帖数: 315 | 53 对总重一半背包。
【在 p*****2 的大作中提到】
: 我写了一个dp的
: static int split(int[] arr)
: {
: int sum=0;
: for(int i : arr)
: sum+=i;
:
: int n=arr.length;
: boolean[] dp=new boolean[sum/2+1];
: dp[0]=true;
|
p*****2
发帖数: 21240 | 54
确实有。改了。
【在 c********t 的大作中提到】
: 似乎有bug
: 测测20,1,4
|
p*****2
发帖数: 21240 | 55
感觉这两个要求区别不大。
【在 c********t 的大作中提到】
: 最后要求是得出两车重量，还是每个包裹的分配？
|
p*****2
发帖数: 21240 | 56
我是说题目的意思差不多。其实解法也是一维到二维。上一个为什么不能套用背包问题
？
【在 c********t 的大作中提到】
: 我觉得差一个条件，一下差得很远。
: 这个是一个 01背包问题 O(n*sum)
: 上一个无法套用背包问题，更难些，时间复杂度是O(n*n*sum)
|
g**********y
发帖数: 14569 | 57 orz, code马上就要freeze，今年工作还差得远的人黯然路过
★ 发自iPhone App: ChineseWeb 7.7
【在 p*****2 的大作中提到】
:
: 我是说题目的意思差不多。其实解法也是一维到二维。上一个为什么不能套用背包问题
: ？
|
p*****2
发帖数: 21240 | 58
现在真不容易见到火鸡大牛现身。其实没活干不是啥好事。
【在 g**********y 的大作中提到】
: orz, code马上就要freeze，今年工作还差得远的人黯然路过
:
: ★ 发自iPhone App: ChineseWeb 7.7
|
c********t
发帖数: 5706 | 59 背包问题是在限定的weight内，选任意多个，最大化value
上一题，首先只能选n/2个，其次value 要最接近sum/2,当时我试过，无法套用。当然
最后也是用DP解决的。
【在 p*****2 的大作中提到】
:
: 现在真不容易见到火鸡大牛现身。其实没活干不是啥好事。
|
c********t
发帖数: 5706 | 60 包裹的分配，要求列出一个车所有的包裹，你的codes就不行了啊
【在 p*****2 的大作中提到】
:
: 现在真不容易见到火鸡大牛现身。其实没活干不是啥好事。
|
|
|
p*****2
发帖数: 21240 | 61
应该改动不大吧？纪录一下就可以了吧。
【在 c********t 的大作中提到】
: 包裹的分配，要求列出一个车所有的包裹，你的codes就不行了啊
|
p*****2
发帖数: 21240 | 62
要最接近sum/2， 这两题都是这个要求吧？ 第一题也不是最大化value吧？
【在 c********t 的大作中提到】
: 背包问题是在限定的weight内，选任意多个，最大化value
: 上一题，首先只能选n/2个，其次value 要最接近sum/2,当时我试过，无法套用。当然
: 最后也是用DP解决的。
|
