|
一组数中寻找加和最接近某个值的组合 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 res = new ArrayList();
/**
*
* @param input 需要产生排列组合的数组
* @param weishu 需要产生排列组合的位数
* @param nowweishu 当前已经完成的位数
* @param nowres 当前已经装入数组的数字
* @param num_weishu 需要使用该位数之后的数字
*/
public void dfs(List input, int weishu, int nowweishu, ArrayList nowres, int num_weishu)//用来产生子集合
{
if(nowweishu == weishu)
{
res.add((ArrayList) nowres.clone());
return;
}
for(int i = num_weishu + 1;i |