输出1到N之间所有相加最接近M的数字组合【可参考更改为背包算法】

昨天查询背包算法，结果很多都是写的贪心算法，而且还有很多是错误的，遂自行写一个。


/**
 * Knapsack.java  V1.0   2016年8月28日 下午6:45:02
 *
 * Copyright [e-mail] All rights reserved.
 *
 * Modification history(By    Time    Reason):
 * 
 * Description:
 */




package com.shopx.util;




import java.util.ArrayList;
import java.util.List;




//如果需要更改成背包算法，那么将ABS判断更改为不大于背包总量


public class MathUtil {




public static void main(final String... args) {
List<Integer> list = new ArrayList<Integer>();
list.add(10);
list.add(5);

list.add(7);
list.add(5);
list.add(8);
list.add(3);
MathUtil k = new MathUtil();
List<Integer> result = new ArrayList<Integer>();
k.near(list,result, 0,18,true);
System.out.println(result);

List<Integer> result2 = new ArrayList<Integer>();
k.near(list,result2, 0,18);

System.out.println(result2);
}




public void near(List<Integer> list,List<Integer> result, int start, int capacity){
near(list, result, start, capacity, false);
}
public void near(List<Integer> list,List<Integer> result, int start, int capacity,boolean minShort) {

//不计算最短路径，那么得到相等之后立即跳出
if(!minShort){
int count = count(result);
if(count == capacity){
return ;
}
}

if(start == list.size()){
return ;
}

int num = 0;
ArrayList<Integer> _result_temp = new ArrayList<Integer>();

ArrayList<Integer> _result = new ArrayList<Integer>();
//计算所有的组合，去绝对值最小的那一个，这里代码可以更简洁，目前仅一个偏移计算，可以在多一个偏移变量进行递归，就不多写了
for (int i = 0; i < list.size(); i++) {
num += list.get(i);
_result_temp.add(list.get(i));
for (int j = start + 1; j < list.size() && j != i; j++) {
_result_temp.add(list.get(j));
if(Math.abs(num - capacity) < Math.abs(count(_result_temp) - capacity) ){
_result_temp.remove(list.get(j));
}else{
num = count(_result_temp);
}
}
num = 0;
if(Math.abs(count(_result_temp) - capacity) < Math.abs(count(_result)  - capacity) ){
_result = (ArrayList<Integer>) _result_temp.clone();
}else if(minShort && Math.abs(count(_result_temp) - capacity) == Math.abs(count(_result)  - capacity)){
//去最短计算路径
if(_result.size() > _result_temp.size()){
_result = (ArrayList<Integer>) _result_temp.clone();
}
}

_result_temp = new ArrayList<Integer>();
}

if(Math.abs(count(result) - capacity) > Math.abs(count(_result)  - capacity) ){
fresh(result,_result);
}else if(minShort && Math.abs(count(result) - capacity) == Math.abs(count(_result)  - capacity)){
//去最短计算路径
if(result.size() > _result.size()){
fresh(result,_result);
}
}
near(list, result, ++start, capacity,minShort);

}




private void fresh(List<Integer> result, ArrayList<Integer> _result) {
result.clear();
for (int i = 0; i < _result.size(); i++) {
result.add(_result.get(i).intValue());
}
}




private int count(List<Integer> result) {
int count = 0;
for (Integer integer : result) {
count += integer;
}
return count;
}




}