Monday, May 16, 2016

Find minimum subset that sum to at least K | Yaozong's Blog

Find minimum subset that sum to at least K | Yaozong's Blog
Given a list of n integers, write a function that outputs the minimum subset of numbers that sum to at least K.
Follow up: can you beat O(nlogn)?
Solution 1: sort and linear search  O(nlogn)

 vector minimum_subset_sum_atleast_K(vector& vec, int K) {   if(vec.size() == 0)       return {};      sort(vec.begin(), vec.end());   int n = vec.size();      vector res(1, vec.back());   int cumsum = vec.back();   for(int i = n - 2; i >= 0; --i)   {     if(vec[i] < 0 || cumsum >= K) break;     cumsum += vec[i];     res.push_back(vec[i]);   }      if(cumsum >= K)       return res;   else       return {}; }
Here we introduce a selection based algorithm which on average costs O(n) but costs O(n^2) in the worst case. The approach is similar to kth order-statistics.

• Randomly choose a pivot from the current array and partition the array into two parts p1 and p2p1 contains integers which are smaller than the pivot; p2 contains integers which are larger than or equal to the pivot.
• Check if pivot + sum(p2) == K, if so, we already find the answer; if not, then if pivot + sum(p2) > K but sum(p2) <= K, we also find the answer; if  sum(p2) > K, we need to do further partition, but we just need to further partition p2;  if pivot + sum(p2) < K,  we need to do further partition, but we need to partition p1 instead and the target value K is updated as K - pivot - sum(p2).
```void find_min_set(int *a, int start, int end, int target)
{

/* generate secret number: */
int s, e, k;

s = start;
e = end;
k = target;

int sum;

while(1)
{
srand ( time(NULL) );
int idx = ((int)rand()) % (e-s + 1) + s;

/* partition and sum */
int tmp = a[idx];
a[idx] = a[e];
a[e] = tmp;

sum = a[e];
int pos = s;
for(int i = s; i < e; i++)
{
if(a[i] < a[e])
{
if(pos != i)
{
tmp = a[pos];
a[pos] = a[i];
a[i] = tmp;
}
pos++;
}
else sum+= a[i];

}

tmp = a[pos];
a[pos] = a[e];
a[e] = tmp;

if(sum == k)
{
cout << "found " << endl;
return;
}
else if(sum > k)
{
if(sum - a[pos] < k)
{
cout << "found " << endl;
return;
}
s = pos + 1;
sum = 0;

}
else
{
k = k - sum;
sum = 0;
e = pos - 1;
}
}

}```
vector<int> quick_select(vector<int>& vec, int i, int j, int K)
{
if(i > j)
return {};
if(i == j)
return {vec[i]};

int len = j - i + 1;
int idx = rand() % len + i;
int pivot = vec[idx];

swap(vec[idx], vec[j]);

int p = i, q = j;
int left_sum = vec[idx], right_sum = 0;

while(p < q) {

if(vec[p] <= pivot) {
left_sum += vec[p];
++ p;
} else {
right_sum += vec[p];
swap(vec[p], vec[--q]);
}

}

swap(vec[q], vec[j]);

vector<int> res;
if(right_sum == K) {
if(q + 1 <= j)
res.insert(res.end(), vec.begin()+q+1, vec.begin()+j+1);
return res;
}
else if(right_sum > K) {
return quick_select(vec, q+1, j, K);
}
else {
if(q + 1 <= j)
res.insert(res.end(), vec.begin()+q+1, vec.begin()+j+1);
K = K - right_sum;
vector<int> res2 = quick_select(vec, i, q, K);
res.insert(res.end(), res2.begin(), res2.end());
return res;
}

}
vector<int> minimum_subset_sum_atleast_K(vector<int>& vec, int K)
{
if(vec.size() == 0)
return {};
vector<int> res = quick_select(vec, 0, vec.size() - 1, K);
int sum = accumulate(res.begin(), res.end(), 0);
if(sum >= K)
return res;
else
return {};
}

https://www.quora.com/Find-the-maximum-sum-of-k-length-subset-of-a-given-set-such-that-sum-is-strictly-less-than-M