java - 算法设计: inserting bags into containers with a limited size

Question

我必须创建一个算法，该算法需要将 n 个行李袋(每个行李袋的重量各不相同)添加到 n 个容器中，每个容器可容纳 50 公斤。每个袋子按顺序装入容器。

行李包重量示例字符串如下(每个数字代表一个包的重量):

16 24 25 3 20 18 7 17 4 15 13 22 2 12 10 5 8 1 11 21 19 6 23 9 14

用行李装满容器有两条规则:

1. 一个容器最多可承载50(公斤)的行李
2. 如果下一个(卸载的)行李会导致容器超重，则将其放入下一个容器

---

我的最终目标是打印每个容器的行李重量 list 。行李袋示例字符串的示例输出为:

Container 1:  16  24
Container 2:  25  3  20 
Container 3:  18  7  17  4
Container 4:  15  13 22
Container 5:  2   12 10  5  8  1  11  
Container 6:  21  19 6 
Container 7:  23  9  14

我当前的代码无法创建容器，我现在正在寻找更好的方法来执行此操作。

public static void insertBagsContainer() {
    ArrayList<ArrayList<Integer>> containerArray = new ArrayList<ArrayList<Integer>>();
    int tempSum = 0;
    int x=0;

    for(int i=0; i<bags.size()-1; i++){
        tempSum = 0;
        ArrayList<Integer> innerBags = new ArrayList<Integer>();
        while (tempSum<= containerWeight){
            tempSum+= bags.get(x);
            innerBags.add(bags.get(x));
            x++;
        }
        containerArray.add(innerBags);
    }
}

Answer 1

使用迭代器的经典示例。

public static void main(String[] args) {
    int maxWeight = 50;

    ArrayList<Integer> containerWeights = new ArrayList<Integer>();
    Integer[] weights = new Integer[] { 16, 24, 25, 3, 20, 18, 7, 17, 4, 15, 13, 22, 2, 12, 10, 5, 8, 1, 11, 21, 19, 6, 23, 9, 14 };

    Iterator<Integer> itr = Arrays.asList(weights).iterator();
    int current = itr.next(); //Get the first weight
    int containerWeight = 0;

    while(itr.hasNext()) {
        if(containerWeight + current > maxWeight) {
            containerWeights.add(containerWeight);
            containerWeight = current;
        } else {
            containerWeight += current;
        }
        current = itr.next();
    }
    containerWeights.add(current);
    System.out.println(Arrays.deepToString(containerWeights.toArray()));
}

打印:[40, 48, 46, 50, 49, 46, 14]