b*****d
发帖数: 15 | 1 You are asked to build a sum by picking one integer from each list. Find the
n largest sums amongst all the combinations of picking an integer from each
list, where n is some positive value. For example if n is 1, then you are
simply expected to find the sum that can be created by adding together the
highest integers in all the lists.
For example, given the lists:
[5,4,3,2,1]
[4,1]
[5,0,0]
[6,4,2]
[1]
and a value of 3 for n your procedure should return the sums
21 (5 + 4 + 5 + 6 + 1)
20 (4 + 4 + 5 + 6 + 1)
19 (3 + 4 + 5 + 6 + 1) |
a********m
发帖数: 15480 | 2 取所有列表最大值的结果是第一个最大值。然后俺顺序去掉的list i的最大值用第二大
代替然后求和，有m个值（m是list数目）取最大的得到第二个最大值。重复到第n个，O
(nm^2). dp应该可以加速一些。 |
c**********e
发帖数: 2007 | 3 First assume each list is sorted already.
Then keep a pointer for each list current[M].
What is the maximum value? It is easy. What is the next? Compare each
current[i]->value - current[i]->next->value and choose the smallest. In
other words, choose the smallest decrease, you get the next largest sum. For
this chosen list, pointer current[i] moves to its next. Repeat this process, you get the the 2nd, 3d, and K-th largest sum.
If lists are all sorted already, the complexity is only O(M*K), where M is
the number of lists and K indicates the K-th largest sum. |
r****t
发帖数: 10904 | 4 这个是 mn (没平方)的吧
，O
【在 a********m 的大作中提到】
: 取所有列表最大值的结果是第一个最大值。然后俺顺序去掉的list i的最大值用第二大
: 代替然后求和，有m个值（m是list数目）取最大的得到第二个最大值。重复到第n个，O
: (nm^2). dp应该可以加速一些。
|
a********m
发帖数: 15480 | 5 如果每次计算m个数的和不cache的话也是m呀。
【在 r****t 的大作中提到】
: 这个是 mn (没平方)的吧
:
: ，O
|
a********m
发帖数: 15480 | |
r****t
发帖数: 10904 | 7 对喔，跟 sliding sum 一样
【在 a********m 的大作中提到】
: 不过弄成O(nm)应该不难。
|
v***a
发帖数: 365 | 8
the
each
Maybe we can use a heap, keep the maximum sum and its selection.
Each step, expand the head one. Totally N step. O(N Log X), X is hard to
calculate. Also need hash.
any other idea?
【在 b*****d 的大作中提到】
: You are asked to build a sum by picking one integer from each list. Find the
: n largest sums amongst all the combinations of picking an integer from each
: list, where n is some positive value. For example if n is 1, then you are
: simply expected to find the sum that can be created by adding together the
: highest integers in all the lists.
: For example, given the lists:
: [5,4,3,2,1]
: [4,1]
: [5,0,0]
: [6,4,2]
|
p*****2
发帖数: 21240 | 9
For
process, you get the the 2nd, 3d, and K-th largest sum.
99 96 1
98 95
97 94
No1. 99+98+97
No2. 96+98+97
按照你的算法
No3. 96+95+97
这个不对吧。你算完第二个数就把99 skip了，可是99还是可以组合其他数呀。
【在 c**********e 的大作中提到】
: First assume each list is sorted already.
: Then keep a pointer for each list current[M].
: What is the maximum value? It is easy. What is the next? Compare each
: current[i]->value - current[i]->next->value and choose the smallest. In
: other words, choose the smallest decrease, you get the next largest sum. For
: this chosen list, pointer current[i] moves to its next. Repeat this process, you get the the 2nd, 3d, and K-th largest sum.
: If lists are all sorted already, the complexity is only O(M*K), where M is
: the number of lists and K indicates the K-th largest sum.
|
g**********y
发帖数: 14569 | 10 我觉得这个应该是期望的解。以前grass贴过。
【在 v***a 的大作中提到】
:
: the
: each
: Maybe we can use a heap, keep the maximum sum and its selection.
: Each step, expand the head one. Totally N step. O(N Log X), X is hard to
: calculate. Also need hash.
: any other idea?
|
|
|
a********m
发帖数: 15480 | 11 计算好第一个和以后，可以把每个列表第一和第二个数的差排序。每次取最小的那个差
对应的列表第一个数字，然后把这个列表后面的差计算出来放进排序数组里面。然后重
复这个步骤。O(max(MlgM, NlgM)), m是列表个数。 |
H***e
发帖数: 476 | 12 没看明白
能否解释下？
我怎么觉得cases非常多
【在 g**********y 的大作中提到】
: 我觉得这个应该是期望的解。以前grass贴过。
|
l****m
发帖数: 64 | |
c**********e
发帖数: 2007 | 14 This is only the special case of m=2.
【在 l****m 的大作中提到】
: 这有个O(k*logk)的
: http://stackoverflow.com/questions/5212037/find-the-kth-largest
|
c**********e
发帖数: 2007 | 15
You are right. Need pointers prev[] to keep previous pointers as well. They
should be enough, though the implementation is different.
【在 p*****2 的大作中提到】
:
: For
: process, you get the the 2nd, 3d, and K-th largest sum.
: 99 96 1
: 98 95
: 97 94
: No1. 99+98+97
: No2. 96+98+97
: 按照你的算法
: No3. 96+95+97
|
c**********e
发帖数: 2007 | 16 一个O(m*n)的解如下。保留一组备用解m个。可以用maximum heap，也可以用数组。每
个备用解含有m个指针指向每个列表的某个节点，以及这m个数值的和。第n步，在
maximum heap和数组中挑出最大的和，就是第n大的和。然后补充进来另一个备用解。
这个备用解就是刚去掉的最大者中依次用各个指针的next取代现指针，并取两个数值变
化最小者。
不知道说清楚了没有。
由于挑选下一个可能的最大解必须尝试至少m种可能，一个O(n*log(m))的解是不可能的
。 |
l****m
发帖数: 64 | 17 No it applies to arbitrary m's. It uses the same optimal structure as the
Dij's solution to shortest path.
Try it on this example and you will see.
【在 c**********e 的大作中提到】
: This is only the special case of m=2.
|
j*****j
发帖数: 201 | 18 这样修改还是有bug吧， 第n+1大的sum不一定是由第n大的和改变一个next指针构成的
，也可以完全重新打乱组成。 比如：
[8,2,1]
[6,4,0]
[3,2,1,0]
小于8+4+1的下一个sum应该是2+6+3. 从8,4,1的next指针是构建不了的。
【在 c**********e 的大作中提到】
: 一个O(m*n)的解如下。保留一组备用解m个。可以用maximum heap，也可以用数组。每
: 个备用解含有m个指针指向每个列表的某个节点，以及这m个数值的和。第n步，在
: maximum heap和数组中挑出最大的和，就是第n大的和。然后补充进来另一个备用解。
: 这个备用解就是刚去掉的最大者中依次用各个指针的next取代现指针，并取两个数值变
: 化最小者。
: 不知道说清楚了没有。
: 由于挑选下一个可能的最大解必须尝试至少m种可能，一个O(n*log(m))的解是不可能的
: 。
|
H***e
发帖数: 476 | 19 exactly
【在 j*****j 的大作中提到】
: 这样修改还是有bug吧， 第n+1大的sum不一定是由第n大的和改变一个next指针构成的
: ，也可以完全重新打乱组成。 比如：
: [8,2,1]
: [6,4,0]
: [3,2,1,0]
: 小于8+4+1的下一个sum应该是2+6+3. 从8,4,1的next指针是构建不了的。
|
j*****j
发帖数: 201 | |
|
|
H***e
发帖数: 476 | 21 应该没有你说的这个问题了
我是这么理解的：
8 2 1
6 4 0
3 2 1
第一步，最大的是 ［8，6，3］ index array is [0 0 0] 那么 push 所有的 (m+1
, n, p), (m, n+1,p), (m,n,p+1) ， 也就是 push [2 6 3] [8 4 3] [8 6 2] 到p-
queue 因为这是所有可能的下一个组合
接着第二大的是[8 6 2] 再push所有 [2 6 2] [ 8 4 2] [8 6 1]到 p-queue里，现在
第三大的一定一经在q里.
以此类推
复杂度，每一步都要expand N个，(N是list的个数）， 所以应该是kN*lg(kN)..
可以用Hashtable to avoid duplicate inserts (thanks to grass)
【在 j*****j 的大作中提到】
: 这个解法也有我说的那个问题
|
c**********e
发帖数: 2007 | 22 也许是我没说清楚，反正你理解得不对—哈哈。
正如Hbase指出的那样，最大解863（17）剔出后，263（11），843（15），862（16）
是第一批备用解。
其中最大的862（16）成为第2大，而离开这个数组。它最大的孩子861（15）填进来。
备用解为263（11），843（15），861（15）。
其中最大的843（15）成为第3大，而离开这个数组。它最大的孩子842（14）填进来。
备用解为263（11），842（14），861（15）。
其中最大的861（15）成为第4大，而离开这个数组。它最大的孩子841（13）填进来。
备用解为263（11），842（14），841（13）。
你说的问题不是问题。但实际上这个解答也有个问题。下一步，其中最大的842（14）
成为第5大，而离开这个数组，它最大的孩子841（13）已经在数组中。这里竟然有三种
选择：
（1） 允许重复，在最后的结果里剔出重复。这样需要多于n个最大值，以便保证有
n个。
（2） 补进842（14）的次大的孩子802（10）。
（3） 补进842（14）的最大的孙子840（12）。
不管是（2）还是（3），都需要标记或者储存这些已经访问过的“节点”。需要储存的
“节点”数是小于m×n的。如果是O（n），这不是问题，但如果是O（m×n），而且如
果每个“节点”都要检查是否已经访问过的话，复杂度就不止O（m×n）了。
【在 j*****j 的大作中提到】
: 这样修改还是有bug吧， 第n+1大的sum不一定是由第n大的和改变一个next指针构成的
: ，也可以完全重新打乱组成。 比如：
: [8,2,1]
: [6,4,0]
: [3,2,1,0]
: 小于8+4+1的下一个sum应该是2+6+3. 从8,4,1的next指针是构建不了的。
|
H***e
发帖数: 476 | 23 你这个有问题的 “它最大的孩子861（15）填进来。” 这里不能只填一个。原因见我
上贴
【在 c**********e 的大作中提到】
: 也许是我没说清楚，反正你理解得不对—哈哈。
: 正如Hbase指出的那样，最大解863（17）剔出后，263（11），843（15），862（16）
: 是第一批备用解。
: 其中最大的862（16）成为第2大，而离开这个数组。它最大的孩子861（15）填进来。
: 备用解为263（11），843（15），861（15）。
: 其中最大的843（15）成为第3大，而离开这个数组。它最大的孩子842（14）填进来。
: 备用解为263（11），842（14），861（15）。
: 其中最大的861（15）成为第4大，而离开这个数组。它最大的孩子841（13）填进来。
: 备用解为263（11），842（14），841（13）。
: 你说的问题不是问题。但实际上这个解答也有个问题。下一步，其中最大的842（14）
|
p*****2
发帖数: 21240 | 24 觉得这个是可以的。但是代码写起来也麻烦。
+1
【在 H***e 的大作中提到】
: 应该没有你说的这个问题了
: 我是这么理解的：
: 8 2 1
: 6 4 0
: 3 2 1
: 第一步，最大的是 ［8，6，3］ index array is [0 0 0] 那么 push 所有的 (m+1
: , n, p), (m, n+1,p), (m,n,p+1) ， 也就是 push [2 6 3] [8 4 3] [8 6 2] 到p-
: queue 因为这是所有可能的下一个组合
: 接着第二大的是[8 6 2] 再push所有 [2 6 2] [ 8 4 2] [8 6 1]到 p-queue里，现在
: 第三大的一定一经在q里.
|
c**********e
发帖数: 2007 | 25 谢谢。受教了。看来O（m×n）是不行的。
【在 H***e 的大作中提到】
: 你这个有问题的 “它最大的孩子861（15）填进来。” 这里不能只填一个。原因见我
: 上贴
|
j*****j
发帖数: 201 | 26 明白了。
不过最后那个问题，做标记似乎增加复杂度太多了....
允许重复的话，每个组合之多重复三次，算第k个最小值求解3k个应该能保证够吧。
【在 c**********e 的大作中提到】
: 也许是我没说清楚，反正你理解得不对—哈哈。
: 正如Hbase指出的那样，最大解863（17）剔出后，263（11），843（15），862（16）
: 是第一批备用解。
: 其中最大的862（16）成为第2大，而离开这个数组。它最大的孩子861（15）填进来。
: 备用解为263（11），843（15），861（15）。
: 其中最大的843（15）成为第3大，而离开这个数组。它最大的孩子842（14）填进来。
: 备用解为263（11），842（14），861（15）。
: 其中最大的861（15）成为第4大，而离开这个数组。它最大的孩子841（13）填进来。
: 备用解为263（11），842（14），841（13）。
: 你说的问题不是问题。但实际上这个解答也有个问题。下一步，其中最大的842（14）
|
f*******t
发帖数: 7549 | 27 写了很长的代码，感觉不太对，如果一个数组里面有重复的数，应该会输出重复的组合
，但程序实际运行结果貌似是没有，不知道为什么。
#include
#include
#include
#include
#include
#define N 5
using namespace std;
struct combination {
int indices[N];
int sum;
combination();
bool operator<(const combination& c) const;
void operator=(const combination& c);
bool operator() (const combination& c) const;
bool operator== (const combination& c) const;
};
combination::combination()
{
sum = 0;
for(int i = 0; i < N; i++)
indices[i] = -1;
}
bool combination::operator<(const combination& c) const
{
return sum < c.sum;
}
void combination::operator=(const combination& c)
{
sum = c.sum;
for(int i = 0; i < N; i++)
indices[i] = (c.indices)[i];
}
bool combination::operator() (const combination& c) const
{
return sum < c.sum;
}
bool combination::operator== (const combination& c) const
{
for(int i = 0; i < N; i++) {
if(indices[i] != (c.indices)[i])
return false;
}
return true;
}
void printCombination(const vector *v, const combination& c)
{
cout << c.sum << " = ";
for(int i = 0; i < N; i++) {
if(i > 0)
cout << " + ";
cout << v[i][(c.indices)[i]];
}
cout << endl;
}
const combination *pick(const vector *v, int *indices)
{
combination *result = new combination;
for(int i = 0; i < N; i++) {
if(indices[i] >= v[i].size()) {
delete result;
return NULL;
}
(result->indices)[i] = indices[i];
result->sum += (v[i])[indices[i]];
}
return result;
}
void rankSums(const vector *v)
{
set used;
int init[N];
for(int i = 0; i < N; i++)
init[i] = 0;
const combination *pC = pick(v, init);
if(pC == NULL) {
cout << "Any empty array?" << endl;
exit(-1);
}
priority_queue, less >
heap;
heap.push(*pC);
delete pC;
pC = NULL;
while(true) {
pC = &heap.top();
used.insert(*pC);
printCombination(v, *pC);
for(int i = 0; i < N; i++)
init[i] = (pC->indices)[i];
heap.pop();
pC = NULL;
for(int i = 0; i < N; i++) {
init[i]++;
pC = pick(v, init);
if(pC) {
if(used.find(*pC) == used.end()) {
heap.push(*pC);
used.insert(*pC);
}
delete pC;
pC = NULL;
}
init[i]--;
}
if(heap.empty())
break;
}
}
int main()
{
vector v[N];
for(int i = 5; i >= 1; i--)
v[0].push_back(i);
v[1].push_back(4);
v[1].push_back(1);
v[2].push_back(5);
v[2].push_back(0);
v[2].push_back(0);
v[3].push_back(6);
v[3].push_back(4);
v[3].push_back(2);
v[4].push_back(1);
rankSums(v);
return 0;
} |
