aaaaaa1q
aaaaaa1q
采纳率33.3%
2014-03-10 14:41

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

已采纳

    小明有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 hz1011 7年前

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

    }

    点赞 评论 复制链接分享
  • mingxuxu mingxuxu 7年前

    对算法没有深入的研究,貌似每个箱子的求和算法+动态规划可以解决这个问题,如果只有4个箱子的话,动态规划算法可能是可以省去的。

    1)求出每个箱子的所有所有可能组合,作为备选序列:
    可以搜索一下,应该是有现成算法的(应该是先排序、再匹配的方式)
    2)将备选序列归并,去掉有冲突(选用了相同数字的)的部分,不断回溯的方式得到结果(有点类似于八皇后问题)。

    点赞 评论 复制链接分享
  • lorewolf311 tianchao_ 7年前

    1:将N个小数排序,将箱子上的数字排序
    2:将箱子上的最小与小数的最大比较,小于的话说明没有可以 只使用一个数 就填满箱子的数。
    3:上面是群举出了一个数的所有可能。接着群举出两个小数组成的和的所有可能,后与箱子上数字比较。
    ...
    ....
    .....
    4:直到n-1个数的所有可能和,最后到n个数的和与箱子上的数字比较,在1、2、3、4期间如果凑满三个箱子,就停止。

    不知道说明白了吗?我觉得可以考虑适当位置写递归方法

    点赞 评论 复制链接分享

相关推荐