aaaaaa1q 2014-03-10 14:41 采纳率: 33.3%
浏览 185
已采纳

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

    小明有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(箱子里的数);

求大能解析算法,万分感谢!

  • 写回答

3条回答 默认 最新

  • hz1011 2014-03-12 15:06
    关注

    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;
    }
    

    }

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(2条)

报告相同问题?

悬赏问题

  • ¥15 arduino控制ps2手柄一直报错
  • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
  • ¥85 maple软件,solve求反函数,出现rootof怎么办?
  • ¥15 求chat4.0解答一道线性规划题,用lingo编程运行,第一问要求写出数学模型和lingo语言编程模型,第二问第三问解答就行,我的ddl要到了谁来求了
  • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
  • ¥50 树莓派安卓APK系统签名
  • ¥65 汇编语言除法溢出问题
  • ¥15 Visual Studio问题
  • ¥20 求一个html代码,有偿
  • ¥100 关于使用MATLAB中copularnd函数的问题