Java:批处理整数

Question

我想知道根据处理时间对一组给定的数字进行批处理的最佳方法是什么。取元素:9, 18, 7, 8, 4, 9, 11, 15, 3, 8,(item 1的处理时间为9，item 2的处理时间为18，以此类推)

如果批处理时间限制设置为 20，则可能的项目分组为:{1, 3, 5} {2} {4, 6} {8, 9} {7, 10}(第 1 组是 9+7+4=20)等所以已经制作了 5 批内容 <= 20 的项目。

理想情况下，我希望它将它们分成尽可能少的组。上面的情况是最少 5 个组，内容限制为 20...

谢谢

Answer 1

If the batch processing time limit is set to say 20,...

所以我假设没有元素大于批处理时间限制。这是我的方法:

• 首先对项目进行排序。然后得到列表的2个指针，一个在索引 0(左指针)和最后一个索引处的另一个(右指针)。
• 获取右指针元素并将其添加到子列表中。采取左指针的元素并将其添加到同一子列表。如果总和子列表中的元素小于限制，更新左指针(设置它到下一个元素)并尝试添加它。继续这个过程直到子列表已满。
• 然后开始填充下一个子列表。消耗所有元素构建子列表。

Java 实现:

int[] input = { 9, 18, 7, 8, 4, 9, 11, 15, 3, 8 }; // Input items.
Arrays.sort(input); // Sort the items.
int left = 0, right = input.length - 1; // Left and right pointers.
int remainder = 0, limit = 20;

// list of groups.
ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();

while (right >= left) 
{
    ArrayList<Integer> subList = new ArrayList<Integer>();
    list.add(subList);
    // Add the current maximum element.
    subList.add(input[right]);
    if (right == left)
        break;
    remainder = limit - input[right];
    right--;

    // Add small elements until limit is reached.
    while (remainder > input[left]) {
        subList.add(input[left]);
        remainder = remainder - input[left];
        left++;
    }

    remainder = 0; // Reset the remainder.
}

打印组:

for (ArrayList<Integer> subList : list) 
{
    for (int i : subList)
        System.out.print(i + " ");
    System.out.println();
}

输出:(每行代表一组数字)

18 
15 3 
11 4 
9 7 
9 8
8