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的数们取或不取得到的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 的大作中提到】
: 不带这么灌水的。
|
