JAVA算法题目：int数组内取数相加凑数

Question

int[] array = new int[] { 460, 588, 720, 1250, 1800, 2200, 3080, 4100,
4375, 5184, 6510, 6900, 9000 };对于上面的数组，取出几个数相加，得到结果为：13750注：每个数只能用一次。求哪几个数相加等于13750；麻烦给段代码。。。

Answer 1

首先观察数组可以排除几个数：588，4375，5184 因为他们如何相加也不会以0结尾。限于篇幅，部分代码如下，剩余的循环可以自己添加下，采用穷举法：
public class DoMain {

public void doit(){
int[] a = new int[] { 460, 720, 1250, 1800, 2200, 3080, 4100,
6510, 6900, 9000 };
for(int i1=0;i1<a.length;i1++){
for(int i2=i1+1;i2<a.length;i2++){
if(a[i1]+a[i2]==13750){
System.out.println(a[i1]+";"+a[i2]);
}
for(int i3=i2+1;i3<a.length;i3++){
if(a[i1]+a[i2]+a[i3]==13750){
System.out.println(a[i1]+";"+a[i2]+";"+a[i3]);
}
for(int i4=i3+1;i4<a.length;i4++){
if(a[i1]+a[i2]+a[i3]+a[i4]==13750){
System.out.println(a[i1]+";"+a[i2]+";"+a[i3]+";"+a[i4]);
}
for(int i5=i4+1;i5<a.length;i5++){
if(a[i1]+a[i2]+a[i3]+a[i4]+a[i5]==13750){
System.out.println(a[i1]+";"+a[i2]+";"+a[i3]+";"+a[i4]+";"+a[i5]);
}
for(int i6=i5+1;i6<a.length;i6++){
if(a[i1]+a[i2]+a[i3]+a[i4]+a[i5]+a[i6]==13750){
System.out.println(a[i1]+";"+a[i2]+";"+a[i3]+";"+a[i4]+";"+a[i5]+";"+a[i6]);
}
for(int i7=i6+1;i7<a.length;i7++){
if(a[i1]+a[i2]+a[i3]+a[i4]+a[i5]+a[i6]+a[i7]==13750){
System.out.println(a[i1]+";"+a[i2]+";"+a[i3]+";"+a[i4]+";"+a[i5]+";"+a[i6]+";"+a[i7]);
}

}
}
}
}
}
}
}

}

public static void main(String[] args) {
DoMain main= new DoMain();
main.doit();
}}

Answer 2

用递归：import java.util.Vector;public class Que1 {
Vector<Vector<Integer>> all=new Vector<Vector<Integer>>();
int[] array = new int[] { 460, 588, 720, 1250, 1800, 2200, 3080, 4100,
4375, 5184, 6510, 6900, 9000 };
public Que1(){
for(int i=0;i<array.length;i++){
Vector<Integer> v=new Vector<Integer>();
pro(v,i);
}
for(int i=0;i<all.size();i++){
System.out.println(all.get(i).toString());
}
}
private boolean pro(Vector<Integer> v,int index){
v.add(array[index]);
int sum=sum(v);
if(sum<=13750){
if(sum==13750){
all.add((Vector<Integer>)v.clone());
v.remove(v.size()-1);
return true;
}
for(int i=index+1;i<array.length;i++){
if(!pro(v,i)){
break;
}
}
v.remove(v.size()-1);
return true;
}else{
v.remove(v.size()-1);
return false;
}
}
private int sum(Vector<Integer> v){
int sum=0;
for(int i=0;i<v.size();i++){
sum+=v.get(i);
}
return sum;
}
public static void main(String arg[]){
new Que1();
}
}本回答被网友采纳

Answer 3

算法分析:得到结果为13750,每个数都比它小,而且三个最小的数相加大于它,因此,测试的开始应该是两个数的相//加,终点是三个数的相加;
具体算法是,依次从数组中取出最接近13750的数,然后作减法,再从数组中取出一个不重复的最接近于差数的数,以次递归的到最后结果
大概思路给你放这了，自己动手做比什么都强！

Answer 4

你的意思是数组中的8个最小的数，加起来要大于13750，就是取出8个数组中最小的数，舍去另外五个大的是么？