Java：批处理整数 [英] Java: batching integers

问题描述

我想知道在处理时间方面批处理给定数字的最佳方法是什么。
取物品： 9,18,7,8,4,9,11,15,3,8，
（第1项有处理时间为9，项目2的处理时间为18，等等。）

I was wondering what the best way is to batch a given set of numbers in terms of a processing time. Take items: 9, 18, 7, 8, 4, 9, 11, 15, 3, 8, (item 1 has a processing time of 9, item 2 has a processing time of 18, etc.)

如果批处理时间限制设置为20，则可能对项目进行分组分批将是： {1,3,5} {2} {4,6} {8,9} {7,10} （第1组是9 + 7 + 4 = 20）等所以已经制作了5批商品，其中的内容是< = 20。

If the batch processing time limit is set to say 20, then a possible grouping of the items into batches would be:{1, 3, 5} {2} {4, 6} {8, 9} {7, 10} (group 1 is 9+7+4=20) etc so 5 batches of items have been made where the contents are <= 20.

理想情况下，我希望它将它们排序为更少的组可能。以上情况至少有5组，内容限制为20 ...

Ideally i want it to sort them into as fewer groups as possible. Above's case is a minimum of 5 groups with a content limit of 20...

谢谢

推荐答案

如果批处理时间限制设置为20，...

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

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

So I assume that there is no element greater than batch processing time limit. Here is my approach:

• 首先对项目进行排序。然后得到2个指针列表，一个是
  索引0（左指针），另一个是最后一个索引
  （右指针）。


• 取右指针元素并将其添加到子列表中。获取左指针的
  元素并将其添加到同一子列表中。如果子列表中的元素
  的总和小于限制，则更新左指针（将
  设置为下一个元素）并尝试添加它。继续此过程，直到填写
  子列表。


• 然后开始填写下一个子列表。将所有元素都消耗到
  构建子列表。

• Firstly sort the items. Then get 2 pointers for the list, one is at index 0 (left-pointer) and the other one at the last index (right-pointer).
• Take the element of right-pointer and add it to a sublist. Take the element of left-pointer and add it to the same sublist. If the sum of the elements in sublist is less than limit, update left-pointer (set it to next element) and try adding it. Continue this process until a sublist is filled.
• Then start filling the next sublist. Consume all elements to construct sublists.

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

输出：（每行代表一组数字）

Output: (Each line denotes a group of numbers)

18 
15 3 
11 4 
9 7 
9 8
8

这篇关于Java：批处理整数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！