求个算法
求arr[]={0.25, 0.5, 1, 2, 4}中任意数相加=6的所有组合,包括自身相加。
[解决办法]
其实这个刚好有个规律，后面的数字都是前面的2倍，那我从后面的两个数字相加，然后开始从这两个数字进行拆，看可以分成几个2几个1等等，这就好了。
但是如果没有规律的话，只能从最大的数字开始相加，然后拆分了。注意：采用回溯法做。
[解决办法]
仅供参考
//问题是这样，有N个数字，数值不同，要列出用他们不同的组合相加等于1000的情况。
//比如，a[3]={200,300,400}
//则有的情况为：
//5 0 0
//3 0 1
//2 2 0
//1 0 2
//0 2 1
//等情况。
#include <stdio.h>
int a[3]={200,300,400};
int temp[3]={0,0,0};
void function(int sum, int index) {
int j,i;
if (sum==1000) {
for (j=0;j<3;j++) printf("%d ",temp[j]);
printf("\n");
return;
} else if (sum>1000) return;
else for (i=index;i<3;i++) {
temp[i]++;
function(sum+a[i],i);
temp[i]--;
}
}
void main() {
function(0,0);
}
//5 0 0
//3 0 1
//2 2 0
//1 0 2
//0 2 1
//
//n个(2<=n<=20)整数(整数范围-10<=x<=10)，判断是否可以从这n个数中找到若干个数，其和为10
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <algorithm>
using namespace std;
int MAXN=20;
int MINN=2;
int x[20];
int n,i,j,k,sum;
int main() {
srand((unsigned)time(NULL));
n=MINN+rand()%(MAXN-1);
for (i=0;i<n;i++) {
x[i]=-10+rand()%21;
printf("%d,",x[i]);
}
printf("\n");
sort(&x[0],&x[n]);
do {
for (i=2;i<=n;i++) {
sum=0;
k=n/2-i/2;
for (j=k;j<k+i;j++) {
sum+=x[j];
}
if (10==sum) {
for (j=k;j<k+i;j++) {
if (j==k+i-1) {
printf("%d==10\n",x[j]);
} else {
printf("%d+",x[j]);
}
}
printf("YES\n");
return 1;
}
}
} while (next_permutation(&x[0],&x[n]));
printf("NO\n");
return 0;
}
#include <utility>
#include <vector>
#include <iostream>
using namespace std;
void printPair(const pair<float,int>& p)
{
for(int i = 0, n = p.second; i < n; ++i){
if(i > 0) cout << "+";
cout << p.first;
}
}
void printVec(const vector<pair<float,int> >& v)
{
for(int i = 0, s = v.size(); i < s; ++i){
if(i > 0) cout << "+";
printPair(v[i]);
}
}
void solve(float arr[], int i, float remain, vector<pair<float,int> >& v)
{
if(remain == 0){
printVec(v);
cout << "\n";
return;
}
if(i < 0) return;
//if can choose arr[i]
if(remain >= arr[i]){
for(int n = remain / arr[i]; n > 0; --n){
v.push_back(make_pair(arr[i], n));
solve(arr, i - 1, remain - n * arr[i], v);
v.pop_back();
}
}
//do not choose arr[i]
solve(arr, i - 1, remain, v);
}
int main()
{
float arr[] = {0.25, 0.5, 1, 2, 4}, target = 6;
vector<pair<float,int> > v;
solve(arr, sizeof(arr)/sizeof(arr[0]) - 1, target, v);
return 0;
}
