B
beyondeast
Unregistered / Unconfirmed
GUEST, unregistred user!
有一个m行n列的矩阵，从每行中取一个数，将这m个数相乘，得到P
如何取得从最大的P到第k大的P这k个序列？
注意：不能将每个P都算出来，然后再排序。
如何取得从最大的P到第k大的P这k个序列？
注意：不能将每个P都算出来，然后再排序。
P
Puma Wang
Unregistered / Unconfirmed
GUEST, unregistred user!
现在开始想。
回家再来答 。
回家再来答 。
Y
yexiaofeng
Unregistered / Unconfirmed
GUEST, unregistred user!
先对每行的数排序，第一列的乘积即为最大的P
然后将第一列中最小的数换成第二列中最大的数（如果两数不相等的话），将第一列最小数
置0。然后执行上一句话的操作就得到Pk-1，依此类推。
然后将第一列中最小的数换成第二列中最大的数（如果两数不相等的话），将第一列最小数
置0。然后执行上一句话的操作就得到Pk-1，依此类推。
B
beyondeast
Unregistered / Unconfirmed
GUEST, unregistred user!
to Puma Wang:
多谢关照
to yexiaofeng:
请注意：不同行的数字不能互相交换，也就是说，第i行的数字不能拿到第j行去用。
多谢关照
to yexiaofeng:
请注意：不同行的数字不能互相交换，也就是说，第i行的数字不能拿到第j行去用。
蒋
蒋劲刚
Unregistered / Unconfirmed
GUEST, unregistred user!
对一行中的数是否可以多次取出？
9 8 7
6 5 4
3 2 1
最大是 9*6*3 ，当取第二次时，第一行的9 是否还可以取出？
9 8 7
6 5 4
3 2 1
最大是 9*6*3 ，当取第二次时，第一行的9 是否还可以取出？
B
beyondeast
Unregistered / Unconfirmed
GUEST, unregistred user!
to 蒋劲刚
可以.
因此一共有n^m个序列
可以.
因此一共有n^m个序列
Z
zyy04
Unregistered / Unconfirmed
GUEST, unregistred user!
注：假设均为正数！！！
1。先排序使得每行第一个数最大，第一列的乘积即为最大的P
2。排序使得每行第二个数为次大
3。计算每行第一个数/第二个数的值，假设i行的该值最小
4。将i行左移一个，此时第一列的乘积即为目前最大的P'
5。排序使得第i行的第二个数为i行次大
6。goto 3
1。先排序使得每行第一个数最大，第一列的乘积即为最大的P
2。排序使得每行第二个数为次大
3。计算每行第一个数/第二个数的值，假设i行的该值最小
4。将i行左移一个，此时第一列的乘积即为目前最大的P'
5。排序使得第i行的第二个数为i行次大
6。goto 3
蒋
蒋劲刚
Unregistered / Unconfirmed
GUEST, unregistred user!
数值是整数吗？
B
beyondeast
Unregistered / Unconfirmed
GUEST, unregistred user!
to 蒋劲刚
都是正数，但不一定是整数
都是正数，但不一定是整数
B
beyondeast
Unregistered / Unconfirmed
GUEST, unregistred user!
to zyy04:
请注意，矩阵中的数可以重复取出，一共有n^m个序列。
实际上就是要求这n^m个序列的连乘积中由最大到第k大的序列。
请注意，矩阵中的数可以重复取出，一共有n^m个序列。
实际上就是要求这n^m个序列的连乘积中由最大到第k大的序列。
蒋
蒋劲刚
Unregistered / Unconfirmed
GUEST, unregistred user!
这好象是一个np困难问题，我再想想
B
beyondeast
Unregistered / Unconfirmed
GUEST, unregistred user!
to 蒋劲刚
多谢多谢! 费神了..
多谢多谢! 费神了..
L
lnboy
Unregistered / Unconfirmed
GUEST, unregistred user!
好象以前看见过这个题，可惜没有认真听老师讲课
等下个星期算法考试过了再说吧。：）[
]
翻翻笔记，或许有办法。
等下个星期算法考试过了再说吧。：）[
]翻翻笔记，或许有办法。
J
JJams_King
Unregistered / Unconfirmed
GUEST, unregistred user!
请把问题翻过来想，求最小的n^m-k个数组成的序列
然后用生成树，估值，剪支
不难
然后用生成树，估值，剪支
不难
P
Puma Wang
Unregistered / Unconfirmed
GUEST, unregistred user!
我来说说 ：
假设 第 K 行的最大值表示为 ：r(K,1) 次大为 :r(K,2).... (k 为 1......N) .
诚然 ：r(1,1) * r(2,1) *.... * r(n,1) =P1 . 第一组。
现在求第二组 ：替换 ： r(1,1) 到 r(n,1) 中的其中一个的 r(k,1) 为 r(k,2) .
设 ： sqrtN 为 P1 的 N 次方根。
依据是 ：Max (r(k,1) + r(k,2) - SqrtN ) (K 为 1..N )
第二个到 n 个基本上能找到 。
这里也有不太严密。可能需要完善的地方就是这个 找 r(k,1)+r(k,2) -SqrtN .
但是有一点是肯定的是 和这个 sqrtN 是离不开的 。
根据 待求的次大值集合里的元素和它的差 是找 P2,P3,P4 .. 的关键。
这里只是从数学方面提出来，不知道我想的对不对，希望大家斧正。
假设 第 K 行的最大值表示为 ：r(K,1) 次大为 :r(K,2).... (k 为 1......N) .
诚然 ：r(1,1) * r(2,1) *.... * r(n,1) =P1 . 第一组。
现在求第二组 ：替换 ： r(1,1) 到 r(n,1) 中的其中一个的 r(k,1) 为 r(k,2) .
设 ： sqrtN 为 P1 的 N 次方根。
依据是 ：Max (r(k,1) + r(k,2) - SqrtN ) (K 为 1..N )
第二个到 n 个基本上能找到 。
这里也有不太严密。可能需要完善的地方就是这个 找 r(k,1)+r(k,2) -SqrtN .
但是有一点是肯定的是 和这个 sqrtN 是离不开的 。
根据 待求的次大值集合里的元素和它的差 是找 P2,P3,P4 .. 的关键。
这里只是从数学方面提出来，不知道我想的对不对，希望大家斧正。
B
beyondeast
Unregistered / Unconfirmed
GUEST, unregistred user!
to JJams_King,
能讲讲详细过程吗?多谢了, 就怕m和n足够大时，最小的几个值也求不到
能讲讲详细过程吗?多谢了, 就怕m和n足够大时，最小的几个值也求不到
M
MrMengyi
Unregistered / Unconfirmed
GUEST, unregistred user!
listen
比较复杂
比较复杂
Z
zyy04
Unregistered / Unconfirmed
GUEST, unregistred user!
to beyondeast:
sorry,我理解错了
sorry,我理解错了
J
JJams_King
Unregistered / Unconfirmed
GUEST, unregistred user!
1。对于n*m的矩阵，把每行都按小到大（安大到小也可以）排列,
的到新的矩阵
+- -+
| a00 a01 ... a0m |
A0 = | a10 a11 ... a1m |
| ... ... ... ... |
| an0 an1 ... anm |
+- -+
2。生成树的原则是根为A0，从第一行开始，生成树：
(1,A0)
----------+----------
| | ... |
(a00,A1) (a01,A1) ... (a0m,A1)
----------+------------------
| | ... |
(a00*a10,A1) (a01*a11,A1) ... (a0m*a1m,A1)
其中
+- -+
| ai0 ai1 ... aim |
Ai = | ... ... ... ... |
| an0 an1 ... anm |
+- -+
3。估值
比较(a00,A1) (a01,A1)
因为a00<a01，假设max=MAX(A1)表示矩阵A1中选出每行最大的数的乘积，
那么以a00为根的子树里包含的乘积都将比a00*max小。
又有a00*max<a01*max，这表明a00子树的所有乘积，至少有
a01*max,a02*max,...,a0m*max这(m-1)个数比它们大。把这个
数作为子树的估计值。
4。截支
按照这种方法，我们可以给每个子树估值，如果比某颗子树大的
乘积数大于k，则该子树可以被截去。
的到新的矩阵
+- -+
| a00 a01 ... a0m |
A0 = | a10 a11 ... a1m |
| ... ... ... ... |
| an0 an1 ... anm |
+- -+
2。生成树的原则是根为A0，从第一行开始，生成树：
(1,A0)
----------+----------
| | ... |
(a00,A1) (a01,A1) ... (a0m,A1)
----------+------------------
| | ... |
(a00*a10,A1) (a01*a11,A1) ... (a0m*a1m,A1)
其中
+- -+
| ai0 ai1 ... aim |
Ai = | ... ... ... ... |
| an0 an1 ... anm |
+- -+
3。估值
比较(a00,A1) (a01,A1)
因为a00<a01，假设max=MAX(A1)表示矩阵A1中选出每行最大的数的乘积，
那么以a00为根的子树里包含的乘积都将比a00*max小。
又有a00*max<a01*max，这表明a00子树的所有乘积，至少有
a01*max,a02*max,...,a0m*max这(m-1)个数比它们大。把这个
数作为子树的估计值。
4。截支
按照这种方法，我们可以给每个子树估值，如果比某颗子树大的
乘积数大于k，则该子树可以被截去。
J
JJams_King
Unregistered / Unconfirmed
GUEST, unregistred user!
其实更好的估值方法是行从大到小排列
对A0到An-1求最大值。其中，
Ai=[a(k,j)] k=0,1,...,i;
j=0,1,...,m-1
MAX(Ai)定义为Ai中每行最大值的乘积
[哎，打字真累，希望能看懂]
对A0到An-1求最大值。其中，
Ai=[a(k,j)] k=0,1,...,i;
j=0,1,...,m-1
MAX(Ai)定义为Ai中每行最大值的乘积
[哎，打字真累，希望能看懂]