Java:批处理整数

Question

我想知道在处理时间方面批处理给定数字的最佳方法是什么.取物品:(第9, 18, 7, 8, 4, 9, 11, 15, 3, 8, 1项处理时间为9,第2项处理时间为18,等等)

如果批处理时间限制设置为20,则可能将项目分组为批次:( {1, 3, 5} {2} {4, 6} {8, 9} {7, 10}组1为9 + 7 + 4 = 20)等,因此已经制作了5批项目,其中内容为< = 20.

理想情况下,我希望它将它们分组为尽可能少的组.以上情况至少有5组,内容限制为20 ...

谢谢

Answer 1

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

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

• 首先对物品进行排序。然后获取列表的 2 个指针，一个位于索引 0 ( left-pointer )，另一个位于最后一个索引 ( right-pointer )。
• 获取右指针的元素并将其添加到子列表中。取出左指针的元素并将其添加到同一个子列表中。如果子列表中的元素总和小于限制，则更新左指针（将其设置为下一个元素）并尝试添加它。继续这个过程直到子列表被填满。
• 然后开始填充下一个子列表。消耗所有元素来构造子列表。

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