Re: 四年后，刘翔还有什么招数？# Joke - 肚皮舞运动
b*s
1 楼
有一堆包裹，数量一定但未知，每个包裹的重量可能一样，也可能不一样。有两部小车
，设计个算法，使得两辆小车里面的包裹重量尽可能相等。
，设计个算法，使得两辆小车里面的包裹重量尽可能相等。
a*9
2 楼
【 以下文字转载自 HuNan 讨论区 】
发信人: at2009 (鱼民马甲), 信区: HuNan
标 题: 贴个俺小闺女这学期的作业。
发信站: BBS 未名空间站 (Thu Dec 19 19:06:34 2013, 美东)
小闺女这学期的一个英文作业是写本儿童读物。
做完后， 要去读给4年级的小朋友听。
俺读过后， 很喜欢， 上传和大家分享。
希望你们的娃也喜欢。
发信人: at2009 (鱼民马甲), 信区: HuNan
标 题: 贴个俺小闺女这学期的作业。
发信站: BBS 未名空间站 (Thu Dec 19 19:06:34 2013, 美东)
小闺女这学期的一个英文作业是写本儿童读物。
做完后， 要去读给4年级的小朋友听。
俺读过后， 很喜欢， 上传和大家分享。
希望你们的娃也喜欢。
a*6
3 楼
【 以下文字转载自 Olympics 讨论区 】
发信人: LiuXiang123 (Cheater), 信区: Olympics
标 题: Re: 四年后，刘翔还有什么招数？
发信站: BBS 未名空间站 (Wed Aug 15 19:37:06 2012, 美东)
这个傻逼四年后参加残奥会。不过残奥好像没有跨栏，应该考虑把钻狗洞加入比赛项目。
发信人: LiuXiang123 (Cheater), 信区: Olympics
标 题: Re: 四年后，刘翔还有什么招数？
发信站: BBS 未名空间站 (Wed Aug 15 19:37:06 2012, 美东)
这个傻逼四年后参加残奥会。不过残奥好像没有跨栏，应该考虑把钻狗洞加入比赛项目。
l*a
4 楼
数组分两半，使差值最小
好像几周前刚讨论过
【在 b*******s 的大作中提到】
: 有一堆包裹，数量一定但未知，每个包裹的重量可能一样，也可能不一样。有两部小车
: ，设计个算法，使得两辆小车里面的包裹重量尽可能相等。
好像几周前刚讨论过
【在 b*******s 的大作中提到】
: 有一堆包裹，数量一定但未知，每个包裹的重量可能一样，也可能不一样。有两部小车
: ，设计个算法，使得两辆小车里面的包裹重量尽可能相等。
a*9
5 楼
06-16
o*1
6 楼
翔公已堕完，四年当为官。不入行伍中，只在看台间。汉下平胸罩，胡歌满苍天。敢问
普渡女，此诗是抄传？
目。
【在 a********6 的大作中提到】
: 【 以下文字转载自 Olympics 讨论区 】
: 发信人: LiuXiang123 (Cheater), 信区: Olympics
: 标 题: Re: 四年后，刘翔还有什么招数？
: 发信站: BBS 未名空间站 (Wed Aug 15 19:37:06 2012, 美东)
: 这个傻逼四年后参加残奥会。不过残奥好像没有跨栏，应该考虑把钻狗洞加入比赛项目。
普渡女，此诗是抄传？
目。
【在 a********6 的大作中提到】
: 【 以下文字转载自 Olympics 讨论区 】
: 发信人: LiuXiang123 (Cheater), 信区: Olympics
: 标 题: Re: 四年后，刘翔还有什么招数？
: 发信站: BBS 未名空间站 (Wed Aug 15 19:37:06 2012, 美东)
: 这个傻逼四年后参加残奥会。不过残奥好像没有跨栏，应该考虑把钻狗洞加入比赛项目。
p*2
7 楼
大牛帖帖你的解法，学习一下。
【在 l*****a 的大作中提到】
: 数组分两半，使差值最小
: 好像几周前刚讨论过
a*9
8 楼
17-25
H*g
9 楼
人大可戴表，政协亦委员，眼见扶摇起，身轻赛跨栏。
【在 o******1 的大作中提到】
: 翔公已堕完，四年当为官。不入行伍中，只在看台间。汉下平胸罩，胡歌满苍天。敢问
: 普渡女，此诗是抄传？
:
: 目。
【在 o******1 的大作中提到】
: 翔公已堕完，四年当为官。不入行伍中，只在看台间。汉下平胸罩，胡歌满苍天。敢问
: 普渡女，此诗是抄传？
:
: 目。
b*x
10 楼
NP-complete的吧
w*t
11 楼
太牛了，你闺女太厉害了
看来天天啃书能啃出成果来，你也欣慰了，哈哈
这图是谁画的？非常非常漂亮，很合我的口味
难道也是你闺女？是老大还是老二啊？
我家这个根本坐不住看书，唉
看来天天啃书能啃出成果来，你也欣慰了，哈哈
这图是谁画的？非常非常漂亮，很合我的口味
难道也是你闺女？是老大还是老二啊？
我家这个根本坐不住看书，唉
s*a
12 楼
。。。。。。
小鸡肚肠！
【在 o******1 的大作中提到】
: 翔公已堕完，四年当为官。不入行伍中，只在看台间。汉下平胸罩，胡歌满苍天。敢问
: 普渡女，此诗是抄传？
:
: 目。
小鸡肚肠！
【在 o******1 的大作中提到】
: 翔公已堕完，四年当为官。不入行伍中，只在看台间。汉下平胸罩，胡歌满苍天。敢问
: 普渡女，此诗是抄传？
:
: 目。
b*m
13 楼
包裹数量未知，咋整？看来是要找一个流水线策略。
【在 l*****a 的大作中提到】
: 数组分两半，使差值最小
: 好像几周前刚讨论过
l*e
14 楼
蛮好看的。。。
【在 a****9 的大作中提到】
: 17-25
【在 a****9 的大作中提到】
: 17-25
b*m
15 楼
如果包裹数量未知，但是拿到每个包裹的时候重量可知，貌似只能是哪边轻往哪边扔了
？
？
w*t
16 楼
这是出书了吗？画给4年级的看
我家儿子还没满4岁。。。。。。。我自己看
给个链接？
我家儿子还没满4岁。。。。。。。我自己看
给个链接？
l*a
17 楼
这题从来没写过，不过似乎只会写成求组合，n!的复杂度，有点夸张
【在 p*****2 的大作中提到】
:
: 大牛帖帖你的解法，学习一下。
【在 p*****2 的大作中提到】
:
: 大牛帖帖你的解法，学习一下。
w*e
18 楼
这个画得太好了！
l*a
19 楼
忽略了这个条件，似乎更麻烦
【在 b***m 的大作中提到】
: 如果包裹数量未知，但是拿到每个包裹的时候重量可知，貌似只能是哪边轻往哪边扔了
: ？
【在 b***m 的大作中提到】
: 如果包裹数量未知，但是拿到每个包裹的时候重量可知，貌似只能是哪边轻往哪边扔了
: ？
l*o
20 楼
好厉害呀！！！
p*2
21 楼
用两个treemap，nlogn
【在 b***m 的大作中提到】
: 如果包裹数量未知，但是拿到每个包裹的时候重量可知，貌似只能是哪边轻往哪边扔了
: ？
a*9
22 楼
这个是老二自己画的， 也是她写的。
你家牛牛还太小吧， 肯定坐不住。
【在 w********t 的大作中提到】
: 太牛了，你闺女太厉害了
: 看来天天啃书能啃出成果来，你也欣慰了，哈哈
: 这图是谁画的？非常非常漂亮，很合我的口味
: 难道也是你闺女？是老大还是老二啊？
: 我家这个根本坐不住看书，唉
你家牛牛还太小吧， 肯定坐不住。
【在 w********t 的大作中提到】
: 太牛了，你闺女太厉害了
: 看来天天啃书能啃出成果来，你也欣慰了，哈哈
: 这图是谁画的？非常非常漂亮，很合我的口味
: 难道也是你闺女？是老大还是老二啊？
: 我家这个根本坐不住看书，唉
m*s
23 楼
subset sum
【在 b*******s 的大作中提到】
: 有一堆包裹，数量一定但未知，每个包裹的重量可能一样，也可能不一样。有两部小车
: ，设计个算法，使得两辆小车里面的包裹重量尽可能相等。
【在 b*******s 的大作中提到】
: 有一堆包裹，数量一定但未知，每个包裹的重量可能一样，也可能不一样。有两部小车
: ，设计个算法，使得两辆小车里面的包裹重量尽可能相等。
a*9
24 楼
哈哈， 没出书， 全在这儿了。
【在 w********t 的大作中提到】
: 这是出书了吗？画给4年级的看
: 我家儿子还没满4岁。。。。。。。我自己看
: 给个链接？
【在 w********t 的大作中提到】
: 这是出书了吗？画给4年级的看
: 我家儿子还没满4岁。。。。。。。我自己看
: 给个链接？
w*x
25 楼
很奇怪二爷为啥还一直在job版逛？
【在 p*****2 的大作中提到】
:
: 用两个treemap，nlogn
w*t
26 楼
原来是老二啊，年龄不算很大啊
你闺女心里有芳草园啊，太羡慕嫉妒你了
这图很美，文章也很有意思
是不是可以考虑请专门的老师指点一下？有利于将来申请好学校啊
【在 a****9 的大作中提到】
: 哈哈， 没出书， 全在这儿了。
你闺女心里有芳草园啊，太羡慕嫉妒你了
这图很美，文章也很有意思
是不是可以考虑请专门的老师指点一下？有利于将来申请好学校啊
【在 a****9 的大作中提到】
: 哈哈， 没出书， 全在这儿了。
l*a
27 楼
两个heap求median?
ZKSS吧
【在 p*****2 的大作中提到】
:
: 用两个treemap，nlogn
ZKSS吧
【在 p*****2 的大作中提到】
:
: 用两个treemap，nlogn
a*9
28 楼
没这个打算， 随其自然。
【在 w********t 的大作中提到】
: 原来是老二啊，年龄不算很大啊
: 你闺女心里有芳草园啊，太羡慕嫉妒你了
: 这图很美，文章也很有意思
: 是不是可以考虑请专门的老师指点一下？有利于将来申请好学校啊
【在 w********t 的大作中提到】
: 原来是老二啊，年龄不算很大啊
: 你闺女心里有芳草园啊，太羡慕嫉妒你了
: 这图很美，文章也很有意思
: 是不是可以考虑请专门的老师指点一下？有利于将来申请好学校啊
p*2
29 楼
这样可以每天都膜拜你。
【在 w****x 的大作中提到】
:
: 很奇怪二爷为啥还一直在job版逛？
w*t
30 楼
赞淡定，向你学习心态
【在 a****9 的大作中提到】
: 没这个打算， 随其自然。
【在 a****9 的大作中提到】
: 没这个打算， 随其自然。
l*a
31 楼
二爷为啥不能够找新工作？
版上骑驴找马做题的多了，另外也许是个人业余爱好
【在 w****x 的大作中提到】
:
: 很奇怪二爷为啥还一直在job版逛？
版上骑驴找马做题的多了，另外也许是个人业余爱好
【在 w****x 的大作中提到】
:
: 很奇怪二爷为啥还一直在job版逛？
p*2
32 楼
不是heap，是treemap。
这题你不知道包裹的数量，所以要动态分配，而且需要调整。
【在 l*****a 的大作中提到】
: 两个heap求median?
: ZKSS吧
b*m
33 楼
Median没用吧？
【在 l*****a 的大作中提到】
: 两个heap求median?
: ZKSS吧
l*a
34 楼
太难了，学习一下好猫的策略，如果面试见到，直接说不会要求换题
【在 p*****2 的大作中提到】
:
: 不是heap，是treemap。
: 这题你不知道包裹的数量，所以要动态分配，而且需要调整。
【在 p*****2 的大作中提到】
:
: 不是heap，是treemap。
: 这题你不知道包裹的数量，所以要动态分配，而且需要调整。
C*U
35 楼
O(n)近似解不知道行不行啊
这个是cpu的load balance问题吧
【在 b*******s 的大作中提到】
: 有一堆包裹，数量一定但未知，每个包裹的重量可能一样，也可能不一样。有两部小车
: ，设计个算法，使得两辆小车里面的包裹重量尽可能相等。
这个是cpu的load balance问题吧
【在 b*******s 的大作中提到】
: 有一堆包裹，数量一定但未知，每个包裹的重量可能一样，也可能不一样。有两部小车
: ，设计个算法，使得两辆小车里面的包裹重量尽可能相等。
p*2
36 楼
其实也不算难，你模拟一下
两个车装包裹，一个新的包裹过来只会发生4种情况。
假设A车和B车
1. 把新包裹放到A车
2. 把新包裹放到B车
3. 把新包裹放到A车，并且把A车的一个重量小一些的包裹放到B车，使得平衡
4. 跟3相反
你把这四种情况都算一遍，哪个结果最平衡就采用那个就可以了。
【在 l*****a 的大作中提到】
: 太难了，学习一下好猫的策略，如果面试见到，直接说不会要求换题
p*2
37 楼
其实也不是爱好了。主要是我下一年的工作基本也做完了。实在是没事干了。
【在 l*****a 的大作中提到】
: 二爷为啥不能够找新工作？
: 版上骑驴找马做题的多了，另外也许是个人业余爱好
b*m
38 楼
这个需要允许记录所有已装车包裹的重量以及编号，关键是3、4两步怎么策略化。
【在 p*****2 的大作中提到】
:
: 其实也不是爱好了。主要是我下一年的工作基本也做完了。实在是没事干了。
p*2
39 楼
Treemap，所以最后是nlogn的复杂度
【在 b***m 的大作中提到】
:
: 这个需要允许记录所有已装车包裹的重量以及编号，关键是3、4两步怎么策略化。
b*s
40 楼
我表达得不清楚
包裹都已经在那里了，而且每个包裹分量都是知道的
【在 p*****2 的大作中提到】
:
: Treemap，所以最后是nlogn的复杂度
包裹都已经在那里了，而且每个包裹分量都是知道的
【在 p*****2 的大作中提到】
:
: Treemap，所以最后是nlogn的复杂度
p*2
41 楼
数量一定但未知
这句话什么意思？
【在 b*******s 的大作中提到】
: 我表达得不清楚
: 包裹都已经在那里了，而且每个包裹分量都是知道的
l*a
42 楼
就是不知道个数？对吗
【在 b*******s 的大作中提到】
: 我表达得不清楚
: 包裹都已经在那里了，而且每个包裹分量都是知道的
【在 b*******s 的大作中提到】
: 我表达得不清楚
: 包裹都已经在那里了，而且每个包裹分量都是知道的
p*e
43 楼
经典dp,tug of war
背包的变种
【在 b*******s 的大作中提到】
: 有一堆包裹，数量一定但未知，每个包裹的重量可能一样，也可能不一样。有两部小车
: ，设计个算法，使得两辆小车里面的包裹重量尽可能相等。
背包的变种
【在 b*******s 的大作中提到】
: 有一堆包裹，数量一定但未知，每个包裹的重量可能一样，也可能不一样。有两部小车
: ，设计个算法，使得两辆小车里面的包裹重量尽可能相等。
l*a
44 楼
那明年有head count吗？
很希望天天跟二爷学习算法，接受熏陶
【在 p*****2 的大作中提到】
:
: 数量一定但未知
: 这句话什么意思？
很希望天天跟二爷学习算法，接受熏陶
【在 p*****2 的大作中提到】
:
: 数量一定但未知
: 这句话什么意思？
b*m
45 楼
俺treemap用得不好唉。
【在 p*****2 的大作中提到】
:
: 数量一定但未知
: 这句话什么意思？
b*s
46 楼
这么牛
【在 C***U 的大作中提到】
: O(n)近似解不知道行不行啊
: 这个是cpu的load balance问题吧
【在 C***U 的大作中提到】
: O(n)近似解不知道行不行啊
: 这个是cpu的load balance问题吧
b*s
47 楼
忽略这个吧，我表达错了，数量一定，已知
【在 p*****2 的大作中提到】
:
: 数量一定但未知
: 这句话什么意思？
【在 p*****2 的大作中提到】
:
: 数量一定但未知
: 这句话什么意思？
p*2
48 楼
就是red black tree。你希望替换的是difference/2重量的，这样就平衡了。所以找最
接近difference/2的，这是需要logn的时间，就是binary search.
【在 b***m 的大作中提到】
:
: 俺treemap用得不好唉。
p*2
49 楼
不知道能不能挨到明年呢。
【在 l*****a 的大作中提到】
: 那明年有head count吗？
: 很希望天天跟二爷学习算法，接受熏陶
b*m
50 楼
晕哦，题改了，不过数量未知也蛮好玩的。
【在 b*******s 的大作中提到】
: 忽略这个吧，我表达错了，数量一定，已知
p*2
51 楼
那我就是2^n的算法了。上次已经被鄙视过了。DP没想明白。
【在 b*******s 的大作中提到】
: 忽略这个吧，我表达错了，数量一定，已知
b*m
52 楼
RBTree我学得可差了…… :-(
【在 p*****2 的大作中提到】
:
: 那我就是2^n的算法了。上次已经被鄙视过了。DP没想明白。
p*2
53 楼
能不能贴个思路呢？
【在 p*****e 的大作中提到】
: 经典dp,tug of war
: 背包的变种
l*a
54 楼
是你还是你们厂？
【在 p*****2 的大作中提到】
:
: 能不能贴个思路呢？
【在 p*****2 的大作中提到】
:
: 能不能贴个思路呢？
p*2
55 楼
会用就行了。
【在 b***m 的大作中提到】
:
: RBTree我学得可差了…… :-(
p*2
56 楼
估计我不会是最先倒下的。
【在 l*****a 的大作中提到】
: 是你还是你们厂？
p*2
57 楼
跟上次的题差不多。上次是要求数量平分，这个不要求，只是要求重量相近。
b*m
58 楼
关键是都不会用……给稍微讲讲呗。
【在 p*****2 的大作中提到】
: 跟上次的题差不多。上次是要求数量平分，这个不要求，只是要求重量相近。
p*2
59 楼
就是balanced binary search tree, 保证search的复杂度是logn
各个语言都有库类支持。Java是TreeMap, C#是SortedMap啥的吧。
【在 b***m 的大作中提到】
:
: 关键是都不会用……给稍微讲讲呗。
b*s
60 楼
上次题目是最近几天的吗，找了下没找到
【在 p*****2 的大作中提到】
: 跟上次的题差不多。上次是要求数量平分，这个不要求，只是要求重量相近。
【在 p*****2 的大作中提到】
: 跟上次的题差不多。上次是要求数量平分，这个不要求，只是要求重量相近。
l*a
61 楼
3-5周左右
当时没来得及研究
【在 b*******s 的大作中提到】
: 上次题目是最近几天的吗，找了下没找到
当时没来得及研究
【在 b*******s 的大作中提到】
: 上次题目是最近几天的吗，找了下没找到
p*e
62 楼
前面有人说了，就是subset sum，01背包问题。
如果要求数量相等，就是二维01背包。
【在 p*****2 的大作中提到】
:
: 就是balanced binary search tree, 保证search的复杂度是logn
: 各个语言都有库类支持。Java是TreeMap, C#是SortedMap啥的吧。
如果要求数量相等，就是二维01背包。
【在 p*****2 的大作中提到】
:
: 就是balanced binary search tree, 保证search的复杂度是logn
: 各个语言都有库类支持。Java是TreeMap, C#是SortedMap啥的吧。
p*2
63 楼
想了一下，如果重量都是整数，所有包裹的重量为sum的话，复杂度是N*sum。
【在 p*****e 的大作中提到】
: 前面有人说了，就是subset sum，01背包问题。
: 如果要求数量相等，就是二维01背包。
t*a
64 楼
这题可以用布尔线性规划来解决。
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 的大作中提到】
: 有一堆包裹，数量一定但未知，每个包裹的重量可能一样，也可能不一样。有两部小车
: ，设计个算法，使得两辆小车里面的包裹重量尽可能相等。
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
65 楼
明白了，多谢
【在 p*****e 的大作中提到】
: 前面有人说了，就是subset sum，01背包问题。
: 如果要求数量相等，就是二维01背包。
【在 p*****e 的大作中提到】
: 前面有人说了，就是subset sum，01背包问题。
: 如果要求数量相等，就是二维01背包。
p*2
66 楼
我写了一个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;
}
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
67 楼
似乎有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;
测测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
68 楼
最后要求是得出两车重量，还是每个包裹的分配？
【在 b*******s 的大作中提到】
: 有一堆包裹，数量一定但未知，每个包裹的重量可能一样，也可能不一样。有两部小车
: ，设计个算法，使得两辆小车里面的包裹重量尽可能相等。
【在 b*******s 的大作中提到】
: 有一堆包裹，数量一定但未知，每个包裹的重量可能一样，也可能不一样。有两部小车
: ，设计个算法，使得两辆小车里面的包裹重量尽可能相等。
c*t
69 楼
我觉得差一个条件，一下差得很远。
这个是一个 01背包问题 O(n*sum)
上一个无法套用背包问题，更难些，时间复杂度是O(n*n*sum)
【在 p*****2 的大作中提到】
: 跟上次的题差不多。上次是要求数量平分，这个不要求，只是要求重量相近。
这个是一个 01背包问题 O(n*sum)
上一个无法套用背包问题，更难些，时间复杂度是O(n*n*sum)
【在 p*****2 的大作中提到】
: 跟上次的题差不多。上次是要求数量平分，这个不要求，只是要求重量相近。
l*o
70 楼
对总重一半背包。
【在 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 的大作中提到】
: 我写了一个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
71 楼
确实有。改了。
【在 c********t 的大作中提到】
: 似乎有bug
: 测测20,1,4
p*2
72 楼
感觉这两个要求区别不大。
【在 c********t 的大作中提到】
: 最后要求是得出两车重量，还是每个包裹的分配？
p*2
73 楼
我是说题目的意思差不多。其实解法也是一维到二维。上一个为什么不能套用背包问题
？
【在 c********t 的大作中提到】
: 我觉得差一个条件，一下差得很远。
: 这个是一个 01背包问题 O(n*sum)
: 上一个无法套用背包问题，更难些，时间复杂度是O(n*n*sum)
g*y
74 楼
orz, code马上就要freeze，今年工作还差得远的人黯然路过
★ 发自iPhone App: ChineseWeb 7.7
【在 p*****2 的大作中提到】
:
: 我是说题目的意思差不多。其实解法也是一维到二维。上一个为什么不能套用背包问题
: ？
★ 发自iPhone App: ChineseWeb 7.7
【在 p*****2 的大作中提到】
:
: 我是说题目的意思差不多。其实解法也是一维到二维。上一个为什么不能套用背包问题
: ？
p*2
75 楼
现在真不容易见到火鸡大牛现身。其实没活干不是啥好事。
【在 g**********y 的大作中提到】
: orz, code马上就要freeze，今年工作还差得远的人黯然路过
:
: ★ 发自iPhone App: ChineseWeb 7.7
c*t
76 楼
背包问题是在限定的weight内，选任意多个，最大化value
上一题，首先只能选n/2个，其次value 要最接近sum/2,当时我试过，无法套用。当然
最后也是用DP解决的。
【在 p*****2 的大作中提到】
:
: 现在真不容易见到火鸡大牛现身。其实没活干不是啥好事。
上一题，首先只能选n/2个，其次value 要最接近sum/2,当时我试过，无法套用。当然
最后也是用DP解决的。
【在 p*****2 的大作中提到】
:
: 现在真不容易见到火鸡大牛现身。其实没活干不是啥好事。
c*t
77 楼
包裹的分配，要求列出一个车所有的包裹，你的codes就不行了啊
【在 p*****2 的大作中提到】
:
: 现在真不容易见到火鸡大牛现身。其实没活干不是啥好事。
【在 p*****2 的大作中提到】
:
: 现在真不容易见到火鸡大牛现身。其实没活干不是啥好事。
p*2
78 楼
应该改动不大吧？纪录一下就可以了吧。
【在 c********t 的大作中提到】
: 包裹的分配，要求列出一个车所有的包裹，你的codes就不行了啊
p*2
79 楼
要最接近sum/2， 这两题都是这个要求吧？ 第一题也不是最大化value吧？
【在 c********t 的大作中提到】
: 背包问题是在限定的weight内，选任意多个，最大化value
: 上一题，首先只能选n/2个，其次value 要最接近sum/2,当时我试过，无法套用。当然
: 最后也是用DP解决的。
相关阅读