k****f
发帖数: 3794 | 1 给定n个数，排好顺序：
a1 < a2 < a3 ....
假定任何的subset sum都不一样。
现在要求前10个最小的subset sum，能不能动态规划解呢？ |
t****t
发帖数: 6806 | 2 哈哈, 这个我知道.
【在 k****f 的大作中提到】
: 给定n个数，排好顺序：
: a1 < a2 < a3 ....
: 假定任何的subset sum都不一样。
: 现在要求前10个最小的subset sum，能不能动态规划解呢？
|
b***e
发帖数: 1419 | 3 If all you want is the 10 smallest sums, then the problem size is 2^10 =
1024, i.e., O(1). Just get the smallest 10 numbers and brutal force.
If you need to generalize it to k smallest sums, then apply the algorithm
that thrust has in mind. |
r****o
发帖数: 1950 | 4 any hints?
【在 t****t 的大作中提到】
: 哈哈, 这个我知道.
|
r****o
发帖数: 1950 | 5 If the sum can also be the adding result from 3 or more numbers, is it
possible to use dynamic programming?
【在 b***e 的大作中提到】
: If all you want is the 10 smallest sums, then the problem size is 2^10 =
: 1024, i.e., O(1). Just get the smallest 10 numbers and brutal force.
: If you need to generalize it to k smallest sums, then apply the algorithm
: that thrust has in mind.
|
t****t
发帖数: 6806 | 6 给定k个数, 取最小的10个解
加上第k+1个数, 把最小的10个加上a(k+1), 得20个解; 从20个里取出10个最小的.
如此重复
O(NM)
【在 k****f 的大作中提到】
: 给定n个数，排好顺序：
: a1 < a2 < a3 ....
: 假定任何的subset sum都不一样。
: 现在要求前10个最小的subset sum，能不能动态规划解呢？
|
r****o
发帖数: 1950 | 7 我想问一下，怎么理解那个sum,
是只有两个数的和，还是可能是3个或多个数的和?
【在 t****t 的大作中提到】
: 给定k个数, 取最小的10个解
: 加上第k+1个数, 把最小的10个加上a(k+1), 得20个解; 从20个里取出10个最小的.
: 如此重复
: O(NM)
|
t****t
发帖数: 6806 | 8 显然可以任意多个数的和嘛
你要问0个数允不允许, 还算是个问题
【在 r****o 的大作中提到】
: 我想问一下，怎么理解那个sum,
: 是只有两个数的和，还是可能是3个或多个数的和?
|
b***e
发帖数: 1419 | 9 麤
【在 t****t 的大作中提到】
: 显然可以任意多个数的和嘛
: 你要问0个数允不允许, 还算是个问题
|
t****t
发帖数: 6806 | 10 @@我不认识这个字, 您说简单点儿行吗.
【在 b***e 的大作中提到】
: 麤
|
S*********g
发帖数: 5298 | 11 犇
【在 t****t 的大作中提到】
: @@我不认识这个字, 您说简单点儿行吗.
|
t******a
发帖数: 1200 | 12 鑫森淼焱垚壵厽惢掱品舙晶畾磊尛孨众毳麤鱻猋犇驫骉
羴龘贔轰矗嚞芔歮雥叒皛馫靐飍飝刕
【在 S*********g 的大作中提到】
: 犇
|
t****t
发帖数: 6806 | 13 我是文盲, 不过"轰"放在里面合适?
【在 t******a 的大作中提到】
: 鑫森淼焱垚壵厽惢掱品舙晶畾磊尛孨众毳麤鱻猋犇驫骉
: 羴龘贔轰矗嚞芔歮雥叒皛馫靐飍飝刕
|
