超级难题:组合,该如何处理
超级难题:组合
有一堆正整数,组合并令其和在特定范围,要求剩余的最少。例如:20个1,33个2,26个3,8个4,16个5,和在15和20之间。使剩下的最少(当然最好是无剩余,都排上,呵呵).恳求最佳算法!
------解决方案--------------------
#include <iostream>
#include <stack>
using namespace std;
void swap(int &a,int &b);
void qsort(int *a,int low,int high)
{
if(low < high) {
int p = low;
int q = high;
int m = a[low];
while(true)
{
while(a[low] <m) low++;
while(a[high]> m) high--;
if(low <high)
{
swap(a[low],a[high]);
low++;
high--;
}
if(low> high)
break;
}
qsort(a,p,low-1);
qsort(a,high+1,q);
}
}
void swap(int &a,int &b)
{
int temp = a;
a = b;
b=temp;
}
int Max;
int rLow;
int rHigh;
stack <int> s;
void find(int sum,int *a,int i,int size)
{
if((sum+a[i]> rHigh&&sum> rLow)||Max> =size) {
if(s.size()> Max)
{
Max = s.size();
stack <int> copy(s);
cout < < "Max is: " < <Max < <endl;
while(!copy.empty())
{
int temp = copy.top();
cout < <temp < < " ";
copy.pop();
}
cout < <endl;
}
return;
}
if(i> size)
return;
sum+= a[i];
s.push(a[i]);
i++;
find(sum,a,i,size);
int t = s.top();
sum-=t;
s.pop();
find(sum,a,i,size);
}
int main()
{
int n=10;
int number[10] = {2,4,3,6,1,2,4,11,4,5};
qsort(number,0,n-1);
Max = 0;
rLow = 10;
rHigh = 15;
find(0,number,0,10);
}
有一堆正整数,组合并令其和在特定范围,要求剩余的最少。例如:20个1,33个2,26个3,8个4,16个5,和在15和20之间。使剩下的最少(当然最好是无剩余,都排上,呵呵).恳求最佳算法!
------解决方案--------------------
#include <iostream>
#include <stack>
using namespace std;
void swap(int &a,int &b);
void qsort(int *a,int low,int high)
{
if(low < high) {
int p = low;
int q = high;
int m = a[low];
while(true)
{
while(a[low] <m) low++;
while(a[high]> m) high--;
if(low <high)
{
swap(a[low],a[high]);
low++;
high--;
}
if(low> high)
break;
}
qsort(a,p,low-1);
qsort(a,high+1,q);
}
}
void swap(int &a,int &b)
{
int temp = a;
a = b;
b=temp;
}
int Max;
int rLow;
int rHigh;
stack <int> s;
void find(int sum,int *a,int i,int size)
{
if((sum+a[i]> rHigh&&sum> rLow)||Max> =size) {
if(s.size()> Max)
{
Max = s.size();
stack <int> copy(s);
cout < < "Max is: " < <Max < <endl;
while(!copy.empty())
{
int temp = copy.top();
cout < <temp < < " ";
copy.pop();
}
cout < <endl;
}
return;
}
if(i> size)
return;
sum+= a[i];
s.push(a[i]);
i++;
find(sum,a,i,size);
int t = s.top();
sum-=t;
s.pop();
find(sum,a,i,size);
}
int main()
{
int n=10;
int number[10] = {2,4,3,6,1,2,4,11,4,5};
qsort(number,0,n-1);
Max = 0;
rLow = 10;
rHigh = 15;
find(0,number,0,10);
}