n***k
发帖数: 2780 | 1 请教各位大牛指教了：
有N个nonunique numbers, 每个数都是在1到100之间，
请问用什么方法能最快地找出所有的数的排列组合that the total of all numbers in
it is greater than 100? |
n***k
发帖数: 2780 | 2 不可能这里没人会做吧？
in
【在 n***k 的大作中提到】
: 请教各位大牛指教了：
: 有N个nonunique numbers, 每个数都是在1到100之间，
: 请问用什么方法能最快地找出所有的数的排列组合that the total of all numbers in
: it is greater than 100?
|
t********t
发帖数: 5415 | 3 还要排列？比如10-41-50和50-41-10算两组？ |
n***k
发帖数: 2780 | 4 说错了，不算排列，只是组合。
你说的算一组。
【在 t********t 的大作中提到】
: 还要排列？比如10-41-50和50-41-10算两组？
|
y****n
发帖数: 579 | |
w********9
发帖数: 8613 | 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******g
发帖数: 1870 | 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***k
发帖数: 2780 | 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********9
发帖数: 8613 | 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***9
发帖数: 696 | 10 这个先用counting sort, 然后作1－100的组合，O(n)? |
|
|
n***k
发帖数: 2780 | 11 不懂。。。
【在 z***9 的大作中提到】
: 这个先用counting sort, 然后作1－100的组合，O(n)?
|
z***9
发帖数: 696 | 12 counting sort -> array [n] --> array[100]
check a[1]+a[100],
a[2]+a[99], a[2]+a[100]... |
g**e
发帖数: 6127 | 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******r
发帖数: 2999 | 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******g
发帖数: 1870 | 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**e
发帖数: 6127 | 16 组合的个数是2^n
【在 K******g 的大作中提到】
: 如果按照你这种算法的话，如果组合的个数是n^2级别的话，那就不存在小于O（n^2）
: 的算法。
: 这道题目应该说是找出combination的个数。
:
: together
|
y****n
发帖数: 579 | 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********9
发帖数: 8613 | 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********9
发帖数: 8613 | |
s**9
发帖数: 207 | 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;j
cout<
cout<
}
if(level
for(int j=i+1;j
if(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********9
发帖数: 8613 | 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****n
发帖数: 431 | 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****n
发帖数: 431 | 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********9
发帖数: 8613 | 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******g
发帖数: 1870 | 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****q
发帖数: 177 | 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********9
发帖数: 8613 | 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********9
发帖数: 8613 | 28
过分复杂化了。要处理×p1或×p2不在考虑之内的情况。nonunique的情况更复杂。
【在 K******g 的大作中提到】
: 这样子好了，如果*p1+*p2 < 100, 我们用recursive，p3指向p1+1，再在p1+1和p2-1之
: 间找组合，使得这个组合的和大于100-(*p1+*p2)。每次内层找到的组合必须加上外层
: 已经有的组合，这样子就可以把所有的找出来了。
: 不过这样的复杂度会很高的。一个简单的办法就是将数组所有的组合产生出来，然后每
: 个判断。
|
l****q
发帖数: 177 | 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********9
发帖数: 8613 | 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********9
发帖数: 8613 | 31
更确切些：这里是按“价格”递推，而不是按“重量”递推。
【在 w********9 的大作中提到】
:
: 这和我前面的解法是一样的吧？
: 与背包问题的本质（这里没有对总价格的任何要求）和解法相差很大。
|
