(100分求)实现一个算法

Question

      
      在一个double类型的数组中，寻找N个数字加起来比较接近 M 的 这些数字的数组
   
  例如：
     double [] dd = {12,13,14,20,25,45,56,12,78,54,23,56,34,67,98,88,11}; 
     int i=3;
    double total = 234;
  
   如：  在dd 中寻找 3个数字，加起来 总和 最接近(大于小于无所谓)  234                 public double[] getNumberList(int i,double total,double []dd){

 return null;
 }   补充： dd里面的数据都是 >0 的。
   

Answer 1

给你个例子，应该能满足你的需求
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Vector;public class ZuHe {
public static void main(String[] args) {
ZuHe c = new ZuHe(new double[]{12,13,14,20,25,45,56,12,78,54,23,56,34,67,98,88,11}, 234, 4);
c.getResult();
}

private double[] candidates = null;
private double target = 0;
private int count = 0;
Vector<double[]> results = new Vector<double[]>();

public ZuHe(double[] cand, int target, int count){
this.candidates = cand;
this.target = target;
this.count = count;
}

public void getResult(){
sort(candidates);
for(int i=0; i<candidates.length; i++){
if(count == 1){
addResult(new double[]{candidates[i]});
}else{
explore(new double[]{candidates[i]}, i+1);
}
}
double[] sumResults = new double[results.size()];
for(int i=0; i<results.size(); i++){
sumResults[i] = sum(results.get(i));
}
sort(sumResults);
double lastDiff  = Double.MAX_VALUE;
int resultIndex = 0;
for(int i=0; i<sumResults.length; i++){
if(Math.abs(sumResults[i]-target)>lastDiff){
resultIndex = i-1;
break;
}else{
lastDiff = Math.abs(sumResults[i]-target);
resultIndex = i;
}
}
for(int i=0; i<sumResults.length; i++){
if(sum(results.get(i)) == sumResults[resultIndex]){
printResult(results.get(i));
break;
}
}
}

public void explore(double[] curr, int i){
for(int j=i; j<candidates.length; j++){
if(curr.length == count){
addResult(curr);
}else if(curr.length < count){
double[] curr2 = new double[curr.length+1];
System.arraycopy(curr, 0, curr2, 0, curr.length);
curr2[curr2.length-1] = candidates[j];
explore(curr2, j+1);
}
}
}

public double sum(double[] arr){
double sun = 0;
for(int i=0; i<arr.length; i++){
sun += arr[i];
}
return sun;
}

private void sort(double[] org){
List<Double> list = new ArrayList<Double>();
for(int i=0; i<org.length; i++){
list.add(org[i]);
}
Collections.sort(list);
for(int i=0; i<org.length; i++){
org[i] = list.get(i);
}
}

public void addResult(double[] result){
results.add(result);
}

public void printResult(double[] result){
for(int i=0; i<result.length-1; i++){
System.out.print(result[i]+" + ");
}
System.out.println(result[result.length-1]+" = "+sum(result));
}}

Answer 2

   你这个程序，对应数组稍微大一些就不可以，数组个数大于30个，java.lang.OutOfMemoryError，Java heap space 占用太大的开销了！

Answer 3

不好意思这个程序有个bug，我改过了，你试试：
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Vector;public class ZuHe {
public static void main(String[] args) {
//ZuHe c = new ZuHe(new double[]{12,13,14,20,25,45,56,12,78,54,23,56,34,67,98,88,11}, 234, 4);
ZuHe c = new ZuHe(new double[]{5,4,3,2,1}, 2, 2);
c.getResult();
}

private double[] candidates = null;
private double target = 0;
private int count = 0;
Vector<double[]> results = new Vector<double[]>();

public ZuHe(double[] cand, int target, int count){
this.candidates = cand;
this.target = target;
this.count = count;
}

public void getResult(){
//sort(candidates);
for(int i=0; i<candidates.length; i++){
if(count == 1){
addResult(new double[]{candidates[i]});
}else{
explore(new double[]{candidates[i]}, i+1);
}
}
double[] sumResults = new double[results.size()];
for(int i=0; i<results.size(); i++){
sumResults[i] = sum(results.get(i));
}
sort(sumResults);
double lastDiff  = Double.MAX_VALUE;
int resultIndex = 0;
for(int i=0; i<sumResults.length; i++){
if(Math.abs(sumResults[i]-target)>lastDiff){
resultIndex = i-1;
break;
}else{
lastDiff = Math.abs(sumResults[i]-target);
resultIndex = i;
}
}
for(int i=0; i<sumResults.length; i++){
if(sum(results.get(i)) == sumResults[resultIndex]){
printResult(results.get(i));
break;
}
}
}

public void explore(double[] curr, int i){
if(curr.length == count){
addResult(curr);
}else{
for(int j=i; j<candidates.length; j++){
double[] curr2 = new double[curr.length+1];
System.arraycopy(curr, 0, curr2, 0, curr.length);
curr2[curr2.length-1] = candidates[j];
explore(curr2, j+1);
}
}
}

public double sum(double[] arr){
double sun = 0;
for(int i=0; i<arr.length; i++){
sun += arr[i];
}
return sun;
}

private void sort(double[] org){
List<Double> list = new ArrayList<Double>();
for(int i=0; i<org.length; i++){
list.add(org[i]);
}
Collections.sort(list);
for(int i=0; i<org.length; i++){
org[i] = list.get(i);
}
}

public void addResult(double[] result){
results.add(result);
}

public void printResult(double[] result){
for(int i=0; i<result.length-1; i++){
System.out.print(result[i]+" + ");
}
System.out.println(result[result.length-1]+" = "+sum(result));
}}

Answer 4

随机从M个里选N个数相加
o(∩_∩)o...
标记

Answer 5

  这个也会 出现 java.lang.OutOfMemoryError，  你把  results  放到Vector，还是会出现这样的情况的，你是基本上可能的情况放到Vector中处理，要不你再改改。。 嘿嘿 辛苦了。

Answer 6

随机取4个数~
import java.util.Random;public class UseRandom {

public static void find(double[] tt, int i, double total,double wucha){
int count = 0;
int index[] = new int[i];
Random r = new Random();
while(true){
count++;
double temptotal = 0;
for(int j=0;j<i;j++){
//这里还要加判断是否重复index
index[j] = Math.abs(r.nextInt())% tt.length  ;
}
for(int j=0;j<i;j++){
temptotal += tt[index[j]];
}
if( Math.abs(temptotal-total)< wucha ){
for(int j=0;j<i;j++){
System.out.println(tt[index[j]]);
}
System.out.println(count);
break;
}
}
}
public static void main(String[] args){
double [] dd = {12,13,14,20,25,45,56,12,78,54,23,56,34,67,98,88,11};
    int i=3;
    double total = 234; 
    UseRandom.find(dd, i, total, 10.0);
}
}

Answer 7

这个是改进后的算法，你再试试。因为原来给你的程序是在我以前的一个算法上面改的。所以设计上就不是很优。这个个应该是没问题了。
public class ZuHe {
public static void main(String[] args) {
ZuHe c = new ZuHe(new double[]{20,30,12,323,43,23,543,56,324,213,54,65,767,23,43,2,34,55,66,44,1,11,231,321,432,21,34,43,46,47}, 234, 4);
//ZuHe c = new ZuHe(new double[]{5,4,3,2,1}, 2, 2);
c.getResult();
}

private double[] candidates = null;
private double target = 0;
private int count = 0;
double[] results = null;
private double minDiff = Double.MAX_VALUE;

public ZuHe(double[] cand, int target, int count){
this.candidates = cand;
this.target = target;
this.count = count;
}

public void getResult(){
for(int i=0; i<candidates.length; i++){
if(count == 1){
addResult(new double[]{candidates[i]});
}else{
explore(new double[]{candidates[i]}, i+1);
}
}
printResult(results);
}

public void explore(double[] curr, int i){
if(curr.length == count){
addResult(curr);
}else{
for(int j=i; j<candidates.length; j++){
double[] curr2 = new double[curr.length+1];
System.arraycopy(curr, 0, curr2, 0, curr.length);
curr2[curr2.length-1] = candidates[j];
explore(curr2, j+1);
}
}
}

public double sum(double[] arr){
double sun = 0;
for(int i=0; i<arr.length; i++){
sun += arr[i];
}
return sun;
}

public void addResult(double[] result){
if(Math.abs(sum(result)-target)<minDiff){
minDiff = Math.abs(sum(result)-target);
results = result;
}
}

public void printResult(double[] result){
for(int i=0; i<result.length-1; i++){
System.out.print(result[i]+" + ");
}
System.out.println(result[result.length-1]+" = "+sum(result));
}}