日期:2014-05-20  浏览次数:20839 次

一个数据组合算法的问题,求教论坛里各位高人
目前需求是这样的: 我们有一个int型的既定的数M ,然后服务器给了很多数据,经过处理之后都是int型的数据,我们称之为数据N(数据个数随着请求的变化而变化),现在要做的就是,如何使用N中的数据进行组合(加法运算,可能是两数相加、可能是三数相加。当然也有可能直接就是M==N),使得组合的数据经过相加之后得到M的值。比如说,我想得到6 ,但是服务器给我了 1 ,2,3,4,6  那么我得到的组合应该就是

6

2  4

3  3

1  1  4 

1  2  3

四个数相加的情况暂不考虑。

求教论坛的各位大神我该如何设计?本人算法方面不行,自己摸索着用 其中一个元素跟其他的元素进行相加的方法,测试发现第一效率低下,第二没有完全生成我想要的组合。因为这种方法有两方面的问题,如果服务器给我的数据只有一条我需要单独进行处理,第二不能正确生成三数相加的组合。。。。。。求教各位大师。
java组合算法 算法

------解决方案--------------------


import java.util.*;
import static java.lang.System.out;
public class Test24 
{
static ArrayList<Integer> getAdd1Type(final int M ,final ArrayList<Integer> Ns)
{
int size = Ns.size();
int index = size/2;
ArrayList<Integer> returnList = new ArrayList<Integer>();
//这种情况,就要求前部遍历,因为无法定位
if (Ns.get(index) == M)
{

for (int i =0; i<size;i++ )
{
if (Ns.get(i) == M)
{
returnList.add(Ns.get(i));
}
}
return returnList;
}

if (Ns.get(index) > M)
{
//0~index-1
for (int i = 0; i< index; i++ )
{

if (Ns.get(i) == M)
{
returnList.add(Ns.get(i));
}


}
return returnList;
}
else
{
//index+1~size
for (int i = index+1; i< size; i++ )
{

if (Ns.get(i) == M)
{
returnList.add(Ns.get(i));
}
}
return returnList;
}

 
}

static ArrayList<String> getAdd2Type(final int M ,final ArrayList<Integer> Ns)
{
 ArrayList<String> listReturn = new  ArrayList<String>();
//这里应该可以选择反向遍历的方式进行比较
int count = Ns.size();

for (int i = 0; i<count ;i++ )
{
if (Ns.get(i)>=M)
{
continue;
}

for (int j = i+1; j<count ;j++ )
{
if (Ns.get(j)>=M)
{
continue;
}

if ((Ns.get(i) +Ns.get(j))==M )
{
listReturn.add("{"+Ns.get(i)+","+Ns.get(j)+"}");
}
}
}

return listReturn;
}

static ArrayList<String> getAdd3Type(final int M ,final ArrayList<Integer> Ns)
{
 ArrayList<String> listReturn = new  ArrayList<String>();
//这里应该可以选择反向遍历的方式进行比较
int count = Ns.size();

for (int i = 0; i<count ;i++ )