n***k 发帖数: 2780 | 1 【 以下文字转载自 JobHunting 讨论区 】
发信人: nivek (泥瓦客 - 别说爱我,我又卖大葱了), 信区: JobHunting
标 题: 这里聪明人多,来一道面试题
发信站: BBS 未名空间站 (Fri Jun 18 01:46:42 2010, 美东)
请教各位大牛指教了:
有N个nonunique numbers, 每个数都是在1到100之间,
请问用什么方法能最快地找出所有的数的组合that the total of all numbers in
it is greater than 100? |
g********n 发帖数: 2314 | 2 需要所有组合都列出来,还是知道多少个就可以了?
【在 n***k 的大作中提到】 : 【 以下文字转载自 JobHunting 讨论区 】 : 发信人: nivek (泥瓦客 - 别说爱我,我又卖大葱了), 信区: JobHunting : 标 题: 这里聪明人多,来一道面试题 : 发信站: BBS 未名空间站 (Fri Jun 18 01:46:42 2010, 美东) : 请教各位大牛指教了: : 有N个nonunique numbers, 每个数都是在1到100之间, : 请问用什么方法能最快地找出所有的数的组合that the total of all numbers in : it is greater than 100?
|
w********9 发帖数: 8613 | 3 是计算算法的问题吗?
排序: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的各种组合)就不说了。 |
t**d 发帖数: 352 | 4 去homedepot门口找n个劳模,让他们自由排列组合,加过一百的报个数就行了。 |
d*******d 发帖数: 2050 | 5 第一,我认为排序是不必要的。
第二,你的意思我明白了,但是有点小问题。
主要func写在下面,initialize什么的就不写了。
设解的个数为
int func(int *A, int * B, int n, int m, long k){
// A array is the original array
// B array is a marker array
int sum = 0;
if( m == 1){
for( int i =0;i <=n-1; i++){
if( B[i] == 0 && A[i] > k ){
++ sum;
//如果需要输出所有的组合的话,在这里输出marker为1的即可.
}
}
}else {
for( int i = 0; i<=n-1; i++){
if(B[i] == 0] {
B[i] = 1;
//这里可以加点优化,减少一点recursive的
【在 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***k 发帖数: 2780 | 6 all possible combinations that meet the sum with the minimum numbers of
elements.
for example:
50, 40, 30, 10, ...
since (50, 40, 30) is good enough, no need to have (50, 40, 30, 10) as
another one.
【在 g********n 的大作中提到】 : 需要所有组合都列出来,还是知道多少个就可以了?
|
n***k 发帖数: 2780 | 7 yes, it is all about the most efficient algorithm.
each
【在 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***k 发帖数: 2780 | 8 try to find the most efficient algorithm.
i guess sorting first will help a lot. btw, are you looking for jobs? we
have tons of openings.
【在 d*******d 的大作中提到】 : 第一,我认为排序是不必要的。 : 第二,你的意思我明白了,但是有点小问题。 : 主要func写在下面,initialize什么的就不写了。 : 设解的个数为 : int func(int *A, int * B, int n, int m, long k){ : // A array is the original array : // B array is a marker array : int sum = 0; : if( m == 1){ : for( int i =0;i <=n-1; i++){
|
s*******e 发帖数: 4188 | 9 recursion的话ms complexity比较高
【在 d*******d 的大作中提到】 : 第一,我认为排序是不必要的。 : 第二,你的意思我明白了,但是有点小问题。 : 主要func写在下面,initialize什么的就不写了。 : 设解的个数为 : int func(int *A, int * B, int n, int m, long k){ : // A array is the original array : // B array is a marker array : int sum = 0; : if( m == 1){ : for( int i =0;i <=n-1; i++){
|
w********9 发帖数: 8613 | 10
each
我只是给了个框架和大思路,否则不简明。每一步是可以用binaryS(A1到Am的和,在
准备期就被记下
来了)和其它最基本的技巧,跳过很多数的。
【在 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的各种组合)就不说了。
|
|
|
d*******d 发帖数: 2050 | 11 好,根据要求改造一下,
先sort,sort完放在A array里面,由大到小,B还是marker
assumption, 所有数都是正数,
先对A里面所有数加起来求个和S
int func(int *A, int * B, int n, long k, int index, long S){
// A array is the original array
// B array is a marker array
int sum = 0;
// 剩下的不够了,不用找了
if(S < k)
return 0;
for( int i = index; i<=n-1; i++){
B[i] = 1;
if( A[i] >= k ){
// found the combination
// output A[i] where B[i] == 1;
++sum;
}else{
// 选A[i]的往后继续找情况
s
【在 n***k 的大作中提到】 : try to find the most efficient algorithm. : i guess sorting first will help a lot. btw, are you looking for jobs? we : have tons of openings.
|
w********9 发帖数: 8613 | 12
这个新加的要求造成的问题不大。在recursion开始的时候判断一下是否S(m)比A(m)小
就可以了。
每个recursion蜕变成两个更小的recursion,因此和组合是平行的。Complexity:O(2^
N)。记住
每个A(m)是否take out和相关的东西,需要很多memory。避免不了的。
【在 n***k 的大作中提到】 : all possible combinations that meet the sum with the minimum numbers of : elements. : for example: : 50, 40, 30, 10, ... : since (50, 40, 30) is good enough, no need to have (50, 40, 30, 10) as : another one.
|
w********9 发帖数: 8613 | 13 非unique的情况就是麻烦一点,不难。对面试来说,这道题有可能太繁琐了。 |
G*******m 发帖数: 16326 | 14 简单。可以简化成二位数的计算。
1)一位=0
2)二位数:1+100
2+99,2+100
3+98,3+99,3+100,。。。=2550
3)三位数 (1+2)+98 (1+2)+99,(1+2)+100
(1+3)+97,1+3+98,1+3+99,1+3+100 |
G*******m 发帖数: 16326 | 15 4)四位数:
(1+2+3)+100, (1+2+3)+99, ... (1+2+3)+95
...(1+2+4)+100, ..., (1+2+4)+94
...
...(1+3+4)+100, ..., (1+3+4)+93
...
50) 五十位数:
(1+2+...+49)+100, ..., (1+2+...+49) + 50
... |
G*******m 发帖数: 16326 | |
w********9 发帖数: 8613 | |
w********9 发帖数: 8613 | 18 假设A(1)到A(M)的和为C(m)。利用这组和值可以避免做一些不必要的recursion(通
过考虑C(m)是否过小)。 |
s*****m 发帖数: 8094 | 19 你这要死人的吧
each
【在 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的各种组合)就不说了。
|
s*****m 发帖数: 8094 | 20 不带这么灌水的。
【在 G*******m 的大作中提到】 : 4)四位数: : (1+2+3)+100, (1+2+3)+99, ... (1+2+3)+95 : ...(1+2+4)+100, ..., (1+2+4)+94 : ... : ...(1+3+4)+100, ..., (1+3+4)+93 : ... : 50) 五十位数: : (1+2+...+49)+100, ..., (1+2+...+49) + 50 : ...
|
|
|
a*****e 发帖数: 911 | |
w********9 发帖数: 8613 | 22
不是。这里并没有要求个数(总价格)是最大的,因此满足要求的组合更多。
【在 a*****e 的大作中提到】 : 这个不是背包问题?NP hard?
|
a*****e 发帖数: 911 | 23 ah,真的。//低头
法1:brute force: 时间是O(2^N). 每个数取或不取得到一组数,总和>100就count一下。
法2:分成<=100和>100。<=100的数们取或不取得到的set求和,count和>100的。乘以剩下的数取或不取的total number。答案为(2^i-x)*2^(N-i). (i<=100,x<=2^100).时间是O(N).
【在 w********9 的大作中提到】 : : 不是。这里并没有要求个数(总价格)是最大的,因此满足要求的组合更多。
|
r********n 发帖数: 7441 | 24 这个可能性太多了
假设前四个数为 11 30 40 20,它们自然构成一个解
但是居于这四个数,再加上任何剩余其他 N-4个数的任何组合也可以构成一个可行解,
在不考虑要剔出nonunique element的影响下,最坏情况下至多可以有 2^(N-4)可行解
先不说别的,光是打印出这些数就是指数级别了,这个题是不是太瞎掰了
应该再加个条件“从N个数中用尽可能少的数。。。”,或许可以把这N个数先分到十个堆里去: 0-9, 10-19, ... 90-99,这样组合起来比较容易预测大约还需要几个数就够了
【在 n***k 的大作中提到】 : try to find the most efficient algorithm. : i guess sorting first will help a lot. btw, are you looking for jobs? we : have tons of openings.
|
r********n 发帖数: 7441 | 25 背包问题比这个简单
背包问题自己也是NP-hard
【在 a*****e 的大作中提到】 : 这个不是背包问题?NP hard?
|
P*****e 发帖数: 260 | 26 "煞笔"
【在 s*****m 的大作中提到】 : 不带这么灌水的。
|