题目：给定一个具有n个元素的实数集A，一个实数t，一个整数k，请问如何快速的确定该实数集中是否存在一个具有k个元素的子集，其所有元素之和小于等于t？
对于这个问题，我首先想到的是排序，只要找到实数集中最小的k个元素，问题也就解了。但对于完全的排序而言实际上是没有必要的，我们只需要确定最小的k个元素就行了。于是我又想到了快排，它的分治思想用在这里是再合适不过了，我们只需对快排作一些改造可以得到一个很好的解决方案。
- int partition(double *set, int n) {
- int low = 0, high = n - 1;
- double p = set[n - 1];
- while(low < high) {
- while(set[low] <= p && low < high )
- ++ low;
- if (low < high)
- set[high --] = set[low];
- while(set[high] > p && low < high)
- -- high;
- if (low < high)
- set[low ++] = set[high];
- }
- set[low] = p;
- return low;
- }
- int sum(double* set, int n) {
- int i;
- double s = 0;
- for (i = 0; i < n; ++i)
- s += set[i];
- return s;
- }
- void print(double* set, int n) {
- int i;
- for (i = 0; i < n; ++i)
- printf("%lf\t", set[i]);
- }
- int verify(double *set, int n, int k, double t) {
- if (n < k || n == 0)
- return 0;
- int m = partition(set, n);
- if (0 == m)
- m = 1;
- if (m <= k) {
- double s = sum(set, m);
- if (m < k) {
- if (s <= t) {
- print(set, m);
- return verify(set + m, n - m, k - m, t - s);
- }
- else
- return 0;
- }
- else {
- if (s <= t) {
- print(set, m);
- printf("\n");
- return 1;
- }
- else
- return 0;