算法"铺瓦片" JAVA实现

Question

有一个算法上的问题各位同学帮助下

在屋顶上铺瓦片,瓦片的话有不同宽度,假设长度分别为1500mm,2000mm,3000mm等(不固定)等不同的瓦片, 屋顶的长度是16300cm(暂时不考虑宽度), 要求如下

1. 铺设玩的瓦片总宽度超过屋顶长度86mm但又不能超过屋顶长度的1000mm
2. 优先选择长的瓦片来铺设,也就是在如上情况下,优先把3000mm的铺上,再去铺次宽的
3. 剩余最后若有更短的选择,为了节约成本,选择更短的
   现在我的代码如下

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.stream.Collectors;

import org.apache.commons.collections.CollectionUtils;

import lombok.Data;

public class test {
    // 瓦片限制最小值
    private static final Integer MIN = 86;
    // 瓦片限制最大值
    private static final Integer MAX = 1000;

    private static List<TileDTO> list = new ArrayList<>();

    static {
        list.add(new TileDTO(1500));
        list.add(new TileDTO(2000));
        list.add(new TileDTO(3000));
    }

    public static void main(String[] args) {
        System.err.println(get(list, 16300));
    }

    /**
     * 
     * @param list        瓦片数组
     * @param totalLength 屋顶总长度
     * @return
     */
    public static List<TileDTO> get(List<TileDTO> list, Integer totalLength) {
        List<TileDTO> guideRailDTOs = new ArrayList<>(list.size());
        if (CollectionUtils.isEmpty(list)) {
            throw new RuntimeException("瓦片数组为空");
        }
        // 倒序
        list = list.stream().sorted(Comparator.comparing(TileDTO::getLength).reversed())
                .collect(Collectors.toList());
        // 获取最短瓦片长度
        Integer shortest = list.get(list.size() - 1).getLength();
        if (shortest - totalLength > MAX) {
            throw new RuntimeException(String.format("最短瓦片长度不能超过总长度%dmm!", MAX));
        }
        // 最大限制总长
        totalLength += MAX;
        for (int i = 0; i < list.size(); i++) {
            // 当前瓦片
            TileDTO tileDTO = list.get(i);
            // 当前瓦片长度
            Integer length = tileDTO.getLength();
            // 当前瓦片数量
            Integer quantity = 0;
            // 若当前剩余长度大于1000, 并且当前瓦片长度小于等于当前剩余长度
            if (length <= totalLength) {
                // 计算出数量,取商
                quantity = (int) (totalLength / length);
                // 计算出剩余长度
                totalLength -= quantity * length;
                // 计算出比当前长度稍短一些的长度
                if (i != list.size() - 1 && (totalLength > MAX || MAX < MIN + totalLength)
                        && totalLength <  list.get(i + 1).getLength()) {
                    // 将当前瓦片数量减一
                    quantity -= 1;
                    // 当前剩余长度加上去
                    totalLength += length;
                }
            }
            guideRailDTOs.add(new TileDTO(tileDTO.getLength(), quantity));
        }
        return guideRailDTOs;
    }

    @Data
    static class TileDTO {

        /**
         * 瓦片长度
         */
        private Integer length;

        /**
         * 使用瓦片数量
         */
        private Integer quantity;

        public TileDTO(Integer length) {
            this.length = length;
        }

        public TileDTO(Integer length, Integer quantity) {
            this.length = length;
            this.quantity = quantity;
        }
    }

}

但是现在根据我们的代码算出的结果是
3000x5+2000x1

这个结果是有瑕疵的,因为根据我们的最优策略正确答案是 3000x5+1500x1(因为比起2000, 1500符合最优成本)
所以现在请各位同学帮忙看下,我这边算法需要在哪里进行优化

Answer 1

这个可以用背包算法、排料算法，具体的实现，可以 google.