这里聪明人多，来一道面试题 - 未名空间MITBBS历史存档

n*k2010-06-18 07:06

1 楼

请教各位大牛指教了：
有N个nonunique numbers, 每个数都是在1到100之间，
请问用什么方法能最快地找出所有的数的排列组合that the total of all numbers in
it is greater than 100?

n*k2010-06-18 07:06

2 楼

不可能这里没人会做吧？

in

【在 n***k 的大作中提到】

: 请教各位大牛指教了：
: 有N个nonunique numbers, 每个数都是在1到100之间，
: 请问用什么方法能最快地找出所有的数的排列组合that the total of all numbers in
: it is greater than 100?

t*t2010-06-18 07:06

3 楼

还要排列？比如10-41-50和50-41-10算两组？

n*k2010-06-18 07:06

4 楼

说错了，不算排列，只是组合。
你说的算一组。

【在 t********t 的大作中提到】

: 还要排列？比如10-41-50和50-41-10算两组？

y*n2010-06-18 07:06

5 楼

同问？

w*92010-06-18 07:06

6 楼

是计算算法的问题吗？
排序：A1基本问题Q(m)：m (<=N) numbers， A(1) to A(m), to find all combinations each
having a sum greater than S(m).
Take out Am, reduce the question to Q(m-1) for A1 to A(m-1) with S(m-1)=S(m)
-A(m)。
更小的一些细节（比如列出AM到AN的各种组合）就不说了。

K*g2010-06-18 07:06

7 楼

一个更简单的办法：
1）排序，从小到大
2）两个指针，p1 points to the first element, and the p2 points to the
largest element.
3)If *p1+*p2 > 100, all numbers from *p1 to *(p2-1) can have such a
combination with *p2. Then --p2. repeat.
4) if *p1+*p2 <= 100, put a third pointer p3 from p1+1, binary search a value so that *p3>100-(*p1+*p2). Then any number between p3 and p2 together p1 are such as combination. then ++p1, repeat.
5) repeat until p1 and p2 meet.
the total complexity will be O(nlogn).

each
m)

【在 w********9 的大作中提到】

: 是计算算法的问题吗？
: 排序：A1: 基本问题Q(m)：m (<=N) numbers， A(1) to A(m), to find all combinations each
: having a sum greater than S(m).
: Take out Am, reduce the question to Q(m-1) for A1 to A(m-1) with S(m-1)=S(m)
: -A(m)。
: 更小的一些细节（比如列出AM到AN的各种组合）就不说了。

n*k2010-06-18 07:06

8 楼

let me see. this could be a very good solution.

value so that *p3>100-(*p1+*p2). Then any number between p3 and p2 together
p1 are such as combination. then ++p1, repeat.

【在 K******g 的大作中提到】

: 一个更简单的办法：
: 1）排序，从小到大
: 2）两个指针，p1 points to the first element, and the p2 points to the
: largest element.
: 3)If *p1+*p2 > 100, all numbers from *p1 to *(p2-1) can have such a
: combination with *p2. Then --p2. repeat.
: 4) if *p1+*p2 <= 100, put a third pointer p3 from p1+1, binary search a value so that *p3>100-(*p1+*p2). Then any number between p3 and p2 together p1 are such as combination. then ++p1, repeat.
: 5) repeat until p1 and p2 meet.
: the total complexity will be O(nlogn).
:

w*92010-06-18 07:06

9 楼

value so that *p3>100-(*p1+*p2). Then any number between p3 and p2
together p1 are such as combination. then ++p1, repeat.
你这个更复杂。我只是给了个框架和大思路，否则不简明。那个方法每一步也是可以用
binaryS的（A1
到Am的和，在准备期就被记下来了），跳过很多数的。
因为中间要列组合，不可能是O(N*lgN)。

【在 K******g 的大作中提到】

: 一个更简单的办法：
: 1）排序，从小到大
: 2）两个指针，p1 points to the first element, and the p2 points to the
: largest element.
: 3)If *p1+*p2 > 100, all numbers from *p1 to *(p2-1) can have such a
: combination with *p2. Then --p2. repeat.
: 4) if *p1+*p2 <= 100, put a third pointer p3 from p1+1, binary search a value so that *p3>100-(*p1+*p2). Then any number between p3 and p2 together p1 are such as combination. then ++p1, repeat.
: 5) repeat until p1 and p2 meet.
: the total complexity will be O(nlogn).
:

z*92010-06-18 07:06

10 楼

这个先用counting sort, 然后作1－100的组合，O(n)?

n*k2010-06-18 07:06

11 楼

不懂。。。

【在 z***9 的大作中提到】

: 这个先用counting sort, 然后作1－100的组合，O(n)?

z*92010-06-18 07:06

12 楼

counting sort -> array [n] --> array[100]
check a[1]+a[100],
a[2]+a[99], a[2]+a[100]...

g*e2010-06-18 07:06

13 楼

你这怎么会是nlogn，"*p1 to *(p2-1) can have such a combination with *p2"。要
找出p1至p2-1的全组合，难道是O(1)?

value so that *p3>100-(*p1+*p2). Then any number between p3 and p2 together
p1 are such as combination. then ++p1, repeat.

【在 K******g 的大作中提到】

: 一个更简单的办法：
: 1）排序，从小到大
: 2）两个指针，p1 points to the first element, and the p2 points to the
: largest element.
: 3)If *p1+*p2 > 100, all numbers from *p1 to *(p2-1) can have such a
: combination with *p2. Then --p2. repeat.
: 4) if *p1+*p2 <= 100, put a third pointer p3 from p1+1, binary search a value so that *p3>100-(*p1+*p2). Then any number between p3 and p2 together p1 are such as combination. then ++p1, repeat.
: 5) repeat until p1 and p2 meet.
: the total complexity will be O(nlogn).
:

p*r2010-06-18 07:06

14 楼

排序后DP
O(n^2)

value so that *p3>100-(*p1+*p2). Then any number between p3 and p2 together
p1 are such as combination. then ++p1, repeat.

【在 K******g 的大作中提到】

: 一个更简单的办法：
: 1）排序，从小到大
: 2）两个指针，p1 points to the first element, and the p2 points to the
: largest element.
: 3)If *p1+*p2 > 100, all numbers from *p1 to *(p2-1) can have such a
: combination with *p2. Then --p2. repeat.
: 4) if *p1+*p2 <= 100, put a third pointer p3 from p1+1, binary search a value so that *p3>100-(*p1+*p2). Then any number between p3 and p2 together p1 are such as combination. then ++p1, repeat.
: 5) repeat until p1 and p2 meet.
: the total complexity will be O(nlogn).
:

K*g2010-06-18 07:06

15 楼

如果按照你这种算法的话，如果组合的个数是n^2级别的话，那就不存在小于O（n^2）
的算法。
这道题目应该说是找出combination的个数。

together

【在 g**e 的大作中提到】

: 你这怎么会是nlogn，"*p1 to *(p2-1) can have such a combination with *p2"。要
: 找出p1至p2-1的全组合，难道是O(1)?
:
: value so that *p3>100-(*p1+*p2). Then any number between p3 and p2 together
: p1 are such as combination. then ++p1, repeat.

g*e2010-06-18 07:06

16 楼

组合的个数是2^n

【在 K******g 的大作中提到】

: 如果按照你这种算法的话，如果组合的个数是n^2级别的话，那就不存在小于O（n^2）
: 的算法。
: 这道题目应该说是找出combination的个数。
:
: together

y*n2010-06-18 07:06

17 楼

我来贴代码
private static void Combination(Vector array, int start, int k,
int limitsum) {
int remaining = array.size() - start;
if (remaining == k) {
int sum = 0;
for (int i = 0; i < k; i++) {
sum += array.get(start + i);
}
if (sum < limitsum) {
return;
}
for (int i = 0; i < array.size(); i++) {
System.out.print(array.get(i) + " ");
}

w*92010-06-18 07:06

18 楼

k,
只是个算法问题，可以只是理论上的（而不一定有实用性）。最多写个pseudo code就可以了。
另外，写程序还是要多些写comments。

【在 y****n 的大作中提到】

: 我来贴代码
: private static void Combination(Vector array, int start, int k,
: int limitsum) {
: int remaining = array.size() - start;
: if (remaining == k) {
: int sum = 0;
: for (int i = 0; i < k; i++) {
: sum += array.get(start + i);
: }
: if (sum < limitsum) {

w*92010-06-18 07:06

19 楼

三藩版也有讨论。
http://www.mitbbs.com/article_t/SanFrancisco/33200773.html

s*92010-06-18 07:06

20 楼

solution based on back tracking:
#include
using namespace std;
const int N=10;
const int M=10;
//sort a[N] first;
int a[N]={0,0, 2, 3, 4,5,5,8,9,10};
int level=0;
int order[N];
int sum=0;
void comb(int i){
order[level++]=a[i];
sum+=a[i];
if(sum>M){
for(int j=0;jcout<cout<}
if(levelfor(int j=i+1;jif(a[j]!=a[j-1])
comb(j);
}
}
sum-=a[i]

【在 n***k 的大作中提到】

: 请教各位大牛指教了：
: 有N个nonunique numbers, 每个数都是在1到100之间，
: 请问用什么方法能最快地找出所有的数的排列组合that the total of all numbers in
: it is greater than 100?

w*92010-06-18 07:06

21 楼

楼主只是要求方法。写code还是应该加些comment，否则造成费解。质量高些的地方都
是有这个要
求的。
两个没用的0元素是你fill in以便M和N相等？用得上吗？
排序结果用得太少。重复值是可以用两次以上的。
因为有组合，怎么也逃不了某种recursion。把Q（M,S(M))的问题转换成Q(M-1,S(M))和
Q(M-
1,S(M-1)=S(M)-A(M))，排序就很好用上。有重复值时，排序后A(1)to A(M)各个相互不
等同，
每个有count（1）到count（M)。把Q（M,N)的问题转换成Q(M-1,S(M))，
。。。
Q(M-1,S(M)-count（M)*A(M))
其中有些recursion可能会没必要做（当余下的数和太小时）。

【在 s**9 的大作中提到】

: solution based on back tracking:
: #include
: using namespace std;
: const int N=10;
: const int M=10;
: //sort a[N] first;
: int a[N]={0,0, 2, 3, 4,5,5,8,9,10};
: int level=0;
: int order[N];
: int sum=0;

g*n2010-06-18 07:06

22 楼

你这个方式是错的，反例：
1，2，3，50，60，70
按你的方法，*p1 + *p2 = 71 <= 100。然后p3指向50，满足*p3>100-(*p1+*p2)。这
时你
输出1以及50和70之间的数，然后++p1。++p1后，你的方法已经漏过了一个解：
1+2+3+50+60+70。这个解按你的方法永远不会出现了。

a value so that *p3>100-(*p1+*p2). Then any number between p3 and p2
together p1 are such as combination. then ++p1, repeat.

【在 K******g 的大作中提到】

: 一个更简单的办法：
: 1）排序，从小到大
: 2）两个指针，p1 points to the first element, and the p2 points to the
: largest element.
: 3)If *p1+*p2 > 100, all numbers from *p1 to *(p2-1) can have such a
: combination with *p2. Then --p2. repeat.
: 4) if *p1+*p2 <= 100, put a third pointer p3 from p1+1, binary search a value so that *p3>100-(*p1+*p2). Then any number between p3 and p2 together p1 are such as combination. then ++p1, repeat.
: 5) repeat until p1 and p2 meet.
: the total complexity will be O(nlogn).
:

g*n2010-06-18 07:06

23 楼

1. 按你的方法，排序是不需要的
2. 你的方法本质上只是brute遍历的一种实现，时间复杂度仍然是(2^n)，没有任何改进

each
1)=S(m)

【在 w********9 的大作中提到】

: 是计算算法的问题吗？
: 排序：A1: 基本问题Q(m)：m (<=N) numbers， A(1) to A(m), to find all combinations each
: having a sum greater than S(m).
: Take out Am, reduce the question to Q(m-1) for A1 to A(m-1) with S(m-1)=S(m)
: -A(m)。
: 更小的一些细节（比如列出AM到AN的各种组合）就不说了。

w*92010-06-18 07:06

24 楼

必要。有的数可能是有重复的。排序结果可以用来避免重复计算和重复解。
还有，每次recursion是最大的数被taken out。对不少情况，这样做会让Q reduce得快
、真正要做的recursion会少一些。
改进
不是那样的。余下数的总和比S小时，recursion就没有必要做下去了，相应的那些余数
的组合也就免了（当然可能在另外的recursion里没有）。（楼主在san Francisco的版
面上把题目做了个小改动,使得更多的组合不需要做。)
这个问题本身最坏的complexity就是O(2^N)。能做的只是减小2^N前的系数。

【在 g****n 的大作中提到】

: 1. 按你的方法，排序是不需要的
: 2. 你的方法本质上只是brute遍历的一种实现，时间复杂度仍然是(2^n)，没有任何改进
:
: each
: 1)=S(m)

K*g2010-06-18 07:06

25 楼

这样子好了，如果*p1+*p2 < 100, 我们用recursive，p3指向p1+1，再在p1+1和p2-1之
间找组合，使得这个组合的和大于100-(*p1+*p2)。每次内层找到的组合必须加上外层
已经有的组合，这样子就可以把所有的找出来了。
不过这样的复杂度会很高的。一个简单的办法就是将数组所有的组合产生出来，然后每
个判断。

【在 g****n 的大作中提到】

: 你这个方式是错的，反例：
: 1，2，3，50，60，70
: 按你的方法，*p1 + *p2 = 71 <= 100。然后p3指向50，满足*p3>100-(*p1+*p2)。这
: 时你
: 输出1以及50和70之间的数，然后++p1。++p1后，你的方法已经漏过了一个解：
: 1+2+3+50+60+70。这个解按你的方法永远不会出现了。
:
: a value so that *p3>100-(*p1+*p2). Then any number between p3 and p2
: together p1 are such as combination. then ++p1, repeat.

l*q2010-06-18 07:06

26 楼

同感，有点类似duplicate的背包问题
f(i,100) = f(i-1, 100) + f(i, 100 - K*a[i]) (K = 1,2,3,...,k)
排序后，考虑第i种值的情况，有两种可能：
只考虑前i-1种值的情况得出的所有解
除了i-1种值，也加上第i种值，如果这种值的数有k个，则可取1到k次

together

【在 p******r 的大作中提到】

: 排序后DP
: O(n^2)
:
: value so that *p3>100-(*p1+*p2). Then any number between p3 and p2 together
: p1 are such as combination. then ++p1, repeat.

w*92010-06-18 07:06

27 楼

http://www.mitbbs.com/article_t1/SanFrancisco/33200773_0_2.html
发信人: wewill2009 (daluobe), 信区: SanFrancisco
标题: Re: 这里聪明人多，来一道面试题 (转载)
发信站: BBS 未名空间站 (Sat Jun 19 14:03:49 2010, 美东)
不是。这里并没有要求个数(总价格）是最大的，因此满足要求的组合更多。

【在 l****q 的大作中提到】

: 同感，有点类似duplicate的背包问题
: f(i,100) = f(i-1, 100) + f(i, 100 - K*a[i]) (K = 1,2,3,...,k)
: 排序后，考虑第i种值的情况，有两种可能：
: 只考虑前i-1种值的情况得出的所有解
: 除了i-1种值，也加上第i种值，如果这种值的数有k个，则可取1到k次
:
: together

w*92010-06-18 07:06

28 楼

过分复杂化了。要处理×p1或×p2不在考虑之内的情况。nonunique的情况更复杂。

【在 K******g 的大作中提到】

: 这样子好了，如果*p1+*p2 < 100, 我们用recursive，p3指向p1+1，再在p1+1和p2-1之
: 间找组合，使得这个组合的和大于100-(*p1+*p2)。每次内层找到的组合必须加上外层
: 已经有的组合，这样子就可以把所有的找出来了。
: 不过这样的复杂度会很高的。一个简单的办法就是将数组所有的组合产生出来，然后每
: 个判断。

l*q2010-06-18 07:06

29 楼

没有说是一样的
f(i,100) = f(i-1, 100) + f(i, 100 - K*a[i]) (K = 1,2,3,...,k)
f(i,100)是大于100的所有使用了前i种值的集合
当然了，如果转移方程本身有误，还请指正

【在 w********9 的大作中提到】

:
: 过分复杂化了。要处理×p1或×p2不在考虑之内的情况。nonunique的情况更复杂。

w*92010-06-18 07:06

30 楼

这和我前面的解法是一样的吧？
与背包问题的本质（这里没有对总价格的任何要求）和解法相差很大。

【在 l****q 的大作中提到】

: 没有说是一样的
: f(i,100) = f(i-1, 100) + f(i, 100 - K*a[i]) (K = 1,2,3,...,k)
: f(i,100)是大于100的所有使用了前i种值的集合
: 当然了，如果转移方程本身有误，还请指正

w*92010-06-18 07:06

31 楼

更确切些：这里是按“价格”递推，而不是按“重量”递推。

【在 w********9 的大作中提到】

:
: 这和我前面的解法是一样的吧？
: 与背包问题的本质（这里没有对总价格的任何要求）和解法相差很大。