关于#屋顶铺设瓦片#的算法，如何解决？

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

根据您的代码和要求，您需要做出以下调整：

1.计算出最短的瓦片长度shortest，如果shortest超过MAX或者shortest - totalLength > MAX，则应该抛出异常。

2.在for循环中，如果当前剩余长度小于等于MAX，直接退出循环，因为此时无论如何也不能再使用更长的瓦片了。

3.在for循环中，如果当前剩余长度大于MAX，但是当前瓦片长度小于等于MAX，应该尝试使用更短的瓦片来填充剩余长度，这样才能保证成本最优。

下面是修改后的代码：

java
Copy code
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 > MAX || 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;
            // 如果当前剩余长度小于等于MAX，直接退出循环
            if (totalLength <= MAX) {
                break;
            }
            // 如果当前剩余长度大于MAX，但是当前瓦片长度小于等于MAX，
            // 尝试使用更短的瓦片来填充剩余长度，保证成本最优
            if (i != list.size() - 1 && totalLength > list.get(i + 1).getLength() && length <= MAX) {
                for (int j = i + 1; j < list.size(); j++) {
                    Integer shorterLength = list.get(j).getLength();
                    if (shorterLength <= MAX && totalLength > shorterLength) {
                        int shorterQuantity = (int) (totalLength / shorterLength);
                        if (shorterQuantity > 0) {
                            quantity -= 1;
                            totalLength += length;
                            quantity += shorterQuantity;
                            totalLength -= shorterQuantity * shorterLength;
                            break;
                        }
                    }
                }
            }
        }
        guideRailDTOs