一组数中寻找加和最接近某个值的组合 JAVA实现
在一组数中寻找一个子集合，使得这个子集合的数的加和最接近给定的某个值，此外，这些数的类型是浮点数。我第一想到是用01背包问题去解，但是感觉对于整型数好做，浮点数会难以控制精度。再次我给出三种做法，第一种是暴力做法，第二三中方法都是基于蒙特卡洛算法。
1、暴力法
这个方法的思路是使用深度优先遍历将给定数组的所有子集合给出，在代码中，我们按子集合内数字的个数依次给出，例如对于数组[1,2,3]，我们先给出只有一个数字的子集合[1],[2],[3]，再给出两个的和三个的。
import java.util.ArrayList; import java.util.LinkedList; import java.util.List; import java.util.Random; public class baoli { public ArrayList<ArrayList<Double>> res = new ArrayList<>(); /** * * @param input 需要产生排列组合的数组 * @param weishu 需要产生排列组合的位数 * @param nowweishu 当前已经完成的位数 * @param nowres 当前已经装入数组的数字 * @param num_weishu 需要使用该位数之后的数字 */ public void dfs(List<Double> input, int weishu, int nowweishu, ArrayList<Double> nowres, int num_weishu)//用来产生子集合 { if(nowweishu == weishu) { res.add((ArrayList<Double>) nowres.clone()); return; } for(int i = num_weishu + 1;i<input.size();i++) { nowres.add(input.get(i)); dfs(input,weishu,nowweishu+1,nowres,i); nowres.remove(nowres.size()-1); } } public ArrayList<ArrayList<Double>> print(List<Double> input, int weishu) { res = new ArrayList<>(); ArrayList<Double> nowres= new ArrayList<>(); dfs(input,weishu,0,nowres,-1); return res; } public ArrayList<Double> sch_emuration(ArrayList<Double> nums,double target) { double lapse = 10000; ArrayList<Double> res = new ArrayList<>(); for (int i = 1;i<=nums.size();i++) { ArrayList<ArrayList<Double>> ares = print(nums,i); for (int j = 0;j<ares.size();j++) { double thissum = 0; for (int k = 0;k<ares.get(j).size();k++) { thissum+=ares.get(j).get(k); } if (Math.abs(thissum - target)<lapse) { res = (ArrayList<Double>) ares.get(j).clone(); lapse = Math.abs(thissum - target); } } } return res; } public static void main(String args[]) { test t = new test(); Random r = new Random(); ArrayList<Double> nums = new ArrayList<>(); nums.add(8.05);nums.add(6.98);nums.add(6.19);nums.add(5.0);nums.add(22.96);nums.add(4.71);nums.add(4.74);nums.add(4.25); nums.add(6.34);nums.add(2.77);nums.add(7.31);nums.add(3.59);nums.add(19.55); ArrayList<Double> res = t.sch_emuration(nums,84.01); double sum = 0; for (int i=0;i<res.size();i++) { System.out.println(res.get(i)); sum = sum + res.get(i); } System.out.println(sum); } } 复制代码该方法的结果展示： 
2、蒙特卡洛组合法
这个方法使用了随机的思想，每次随机得到一个子集合的数量，再依据这个数量随机选择数组中的数（可以使用HashMap避免重复选择）
import java.util.ArrayList; import java.util.HashMap; import java.util.Random; public class mtkl { public ArrayList<Double> MC_combination(ArrayList<Double> nums,double target) { ArrayList<Double> res = new ArrayList<>(); double lapse = 10000; Random random = new Random(); for (int i=0;i<1000000;i++) { if(i%10000==0) System.out.println(i); int numsize = random.nextInt(nums.size() + 1); ArrayList<Double> ares = new ArrayList<>(); HashMap<Integer,Integer> map = new HashMap<>(); double thissum = 0; for (int j=0 ;j<numsize;j++) { int anumberindex = random.nextInt(nums.size()); while (map.containsKey(anumberindex)) { anumberindex = random.nextInt(nums.size()); } map.put(anumberindex,1); ares.add(nums.get(anumberindex)); thissum += nums.get(anumberindex); } if(Math.abs(thissum - target)<lapse) { lapse = Math.abs(thissum - target); res = (ArrayList<Double>) ares.clone(); } if(lapse<0.000001) break; } return res; } public static void main(String args[]) { Random r = new Random(); ArrayList<Double> nums = new ArrayList<>(); nums.add(8.05);nums.add(6.98);nums.add(6.19);nums.add(5.0);nums.add(22.96);nums.add(4.71);nums.add(4.74);nums.add(4.25); nums.add(6.34);nums.add(2.77);nums.add(7.31);nums.add(3.59);nums.add(19.55); mtkl m = new mtkl(); ArrayList<Double> res = m.MC_combination(nums,84.01); double sum = 0; for (int i=0;i<res.size();i++) { System.out.println(res.get(i)); sum = sum + res.get(i); } System.out.println(sum); System.out.println(Math.abs(sum - 84.01)); } }; 复制代码该方法的结果展示：
3、蒙特卡洛排列法
这个方法也是基于随机算法。该方法的思想是在每次计算前，都对数组进行一次打乱顺序，然后从头加和，直到加和的值大于给定目标值。这个方法没有前两个精度高，而且运算次数大于前两个，因此可以当一个思路。
import java.util.ArrayList; import java.util.Collections; import java.util.Random; public class mtkl2 { public ArrayList<Double> MC_permutation(ArrayList<Double> nums,double target) { ArrayList<Double> res = new ArrayList<>(); for (int i=0;i<9000000;i++) { double lapse = 10000; ArrayList<Double> newnum = (ArrayList<Double>) nums.clone(); Collections.shuffle(newnum); double lastsum = 0; ArrayList<Double> alist = new ArrayList<>(); for (int j = 0;j< newnum.size();j++) { double thissum = lastsum + newnum.get(j); if(thissum>target) { double ds1 = Math.abs(lastsum - target); double ds2 = Math.abs(thissum - target); double ds = Math.min(ds1,ds2); if(ds<lapse) { lapse = ds; if(ds1<ds2) { res = (ArrayList<Double>) alist.clone(); } else { alist.add(newnum.get(j)); res = (ArrayList<Double>) alist.clone(); } break; } } alist.add(newnum.get(j)); lastsum = thissum; } if(lapse<0.00001) break; } return res; } public static void main(String args[]) { ArrayList<Double> nums = new ArrayList<>(); nums.add(8.05);nums.add(6.98);nums.add(6.19);nums.add(5.0);nums.add(22.96);nums.add(4.71);nums.add(4.74);nums.add(4.25); nums.add(6.34);nums.add(2.77);nums.add(7.31);nums.add(3.59);nums.add(19.55); mtkl2 m = new mtkl2(); ArrayList<Double> res = m.MC_permutation(nums,84.01); double sum = 0; for (int i=0;i<res.size();i++) { System.out.println(res.get(i)); sum = sum + res.get(i); } System.out.println(sum); System.out.println(Math.abs(sum - 84.01)); } } 复制代码该方法的结果展示：
作者：lizefeng1998
链接：https://juejin.cn/post/7023646498713927717