一个有趣的拼数游戏，没有头绪

Question

    小明有4个箱子，箱子上写有指定的数，如（452.11,684.22,847.49,357.36）。地上堆着一堆已确定的N个小数。如（12.1,1.21,8.9,32.5等等）。

    现在，小明要将这些杂乱的小数放入到4个盒子中，使得至少有三个盒子里的小数之和等于箱子上写明的指定数值。

即：452.11（箱子指定数值）=58.14+89.36+42.39+97.85+45.99+84.21+44.44（箱子里的数）；

求大能解析算法，万分感谢！

Answer 1

public class TestClass {
public static void main(String[] args) throws ParseException {
// 地上的数字
List littleNumbers = new ArrayList();
littleNumbers.add(1.1);
littleNumbers.add(2.1);
littleNumbers.add(8.1);
littleNumbers.add(9.1);
littleNumbers.add(1.0);
littleNumbers.add(2.0);
littleNumbers.add(3.0);

    // 箱子上的数字
    List<Double> boxNumbers = new ArrayList<Double>();
    boxNumbers.add(1.0);
    boxNumbers.add(2.0);
    boxNumbers.add(3.0);
    boxNumbers.add(10.2);

    getResult(boxNumbers, 0, littleNumbers, 0, 4);
}

/**
 * 查找littleNumbers中有没有加起来等于boxNumbers中第index个数字的情况。
 * 
 * @param boxNumbers 箱子上的数字
 * @param index 传入index以便递归遍历
 * @param littleNumbers 地上的小数
 * @param currentFind 当前已经填好的箱子数
 * @param occour 需要填好的箱子数
 * @return
 */
public static boolean getResult(List<Double> boxNumbers, int index,
        List<Double> littleNumbers, int currentFind, int needToFind) {

    // 尝试把数字放到所有箱子里去，再看看放好的箱子数是不是满足要求
    if (index == boxNumbers.size()) {
        if (currentFind >= needToFind) {
            System.out.println("找到一次满足的情况！");
            return true;
        } else {
            return false;
        }
    }
    SplitIterator iterator = new Splitor(littleNumbers,
            boxNumbers.get(index));
    SplitResult result = null;
    do {
        result = iterator.next();
        int tempFind = currentFind;
        if (result.isSuccess()) {
            tempFind++;
        }
        boolean isOK = getResult(boxNumbers, index + 1,
                result.getRestList(), tempFind, needToFind);
        // 这里可以把找到的数组打印出来，只能打印第一次找到的情况
        // if (isOK) {
        // System.out.println("Box Number " + index + " ("
        // + boxNumbers.get(index) + ") :"
        // + result.getResultList());
        // return true;
        // }
    } while (result.isSuccess());
    return false;
}

}

/**

• 计算结果类
  /
  class SplitResult {
  /*

  • 是否找到结果 */ private boolean success;

  /**

  • 加起来等于箱子上的数字,没有则为空list */ private List resultList;

  /**

  • 剩下的数字，没找到的话则为初始输入的list */ private List restList;

  public boolean isSuccess() {
  return success;
  }

  public void setSuccess(boolean success) {
  this.success = success;
  }

  public List getResultList() {
  return resultList;
  }

  public void setResultList(List resultList) {
  this.resultList = resultList;
  }

  public List getRestList() {
  return restList;
  }

  public void setRestList(List restList) {
  this.restList = restList;
  }

}

/**

• 从一个list中找出相加等于某个double值的数字
  /
  interface SplitIterator {
  /*

  • 每调用一次next，就返回一种可能的情况，SplitResult.isSuccess()为false则找不到 */ public SplitResult next();

  public void setLittleNumbers(List littleNumbers);

  public List getLittleNumbers();

  public double getBoxNumber();

  public void setBoxNumber(double boxNumber);

}

class Splitor implements SplitIterator {

private List<Double> littleNumbers = new ArrayList<Double>();

private double boxNumber;

private boolean end = false;

private List<Integer> sequenceList = new ArrayList<Integer>();

public Splitor() {
}

public Splitor(List<Double> list, double boxNumber) {
    this.littleNumbers.addAll(list);
    this.boxNumber = boxNumber;
}

public SplitResult next() {
    while (!checkEnd()) {
        double tempSum = 0.0;
        for (int i = 0; i < sequenceList.size(); i++) {
            tempSum += littleNumbers.get(sequenceList.get(i));
        }

        if ((boxNumber - tempSum) < 0.000001
                && (boxNumber - tempSum) > -0.000001) {
            return getResult();
        }
    }
    SplitResult result = new SplitResult();
    result.setSuccess(false);
    result.setResultList(new ArrayList<Double>());
    List<Double> restList = new ArrayList<Double>();
    restList.addAll(littleNumbers);
    result.setRestList(restList);
    return result;
}

/**
 * 查找成功，返回结果
 */
private SplitResult getResult() {
    List<Double> resultList = new ArrayList<Double>();
    List<Double> restList = new ArrayList<Double>();
    restList.addAll(littleNumbers);
    for (int i = sequenceList.size() - 1; i >= 0; i--) {
        int index = sequenceList.get(i);
        restList.remove(index);
        resultList.add(littleNumbers.get(index));
    }
    SplitResult result = new SplitResult();
    result.setSuccess(true);
    result.setResultList(resultList);
    result.setRestList(restList);
    return result;
}

/**
 * 从1个数到数组中所有数字相加的情况
 */
private boolean checkEnd() {
    if (end) {
        return true;
    }
    if (sequenceList.isEmpty()) {
        sequenceList.add(0);
        return false;
    }
    for (int i = sequenceList.size() - 1; i >= 0; i--) {
        if (sequenceList.get(i) < (littleNumbers.size()
                - sequenceList.size() + i)) {
            int index = sequenceList.get(i);
            for (int j = i; j < sequenceList.size(); j++) {
                sequenceList.set(j, ++index);
            }
            return false;
        }
    }
    if (sequenceList.size() < littleNumbers.size()) {
        int size = sequenceList.size();
        sequenceList.clear();
        for (int i = 0; i <= size; i++) {
            sequenceList.add(i);
        }
        return false;
    }
    end = true;
    return true;
}

public List<Double> getLittleNumbers() {
    return littleNumbers;
}

public void setLittleNumbers(List<Double> littleNumbers) {
    this.littleNumbers = littleNumbers;
}

public double getBoxNumber() {
    return boxNumber;
}

public void setBoxNumber(double boxNumber) {
    this.boxNumber = boxNumber;
}

}