Java：批处理整数
我想知道在处理时间方面批处理给定数字的最佳方法是什么。 取项目： 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 …
谢谢
如果批处理时间限制设置为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> list = new ArrayList>(); while (right >= left) { ArrayList subList = new ArrayList (); 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 subList : list) { for (int i : subList) System.out.print(i + " "); System.out.println(); }
输出:(每行代表一组数字）
18 15 3 11 4 9 7 9 8 8
- 从IN组中取出最大值并放入一组新的S.（第2项，值18）
- 尝试找到值<=（20 - 18）的最大项：无，将S添加到集合列表中。
- 如果IN不是空的GOTO 1
迭代：
IN: 9, 18, 7, 8, 4, 9, 11, 15, 3, 8 S1 (18) : 2:18 IN: 9, _, 7, 8, 4, 9, 11, 15, 3, 8 S2 (19) : 8:15, 5:4 IN: 9, _, 7, 8, _, 9, 11, _, 3, 8 S3 (20) : 7:11, 1:9 IN: _, _, 7, 8, _, 9, _, _, 3, 8 S4 (20) : 6: 9, 4:8, 0:3 IN: _, _, 7, _, _, _, _, _, _, 8 S5 (15) : 10: 8, 3:7 IN: _, _, _, _, _, _, _, _, _, _
代码 ：
public class Knapsack { public static void knapsack( int capacity, int[] values, List< int[] > indices ) { int[] in = Arrays.copyOf( values, values.length ); List< Integer > workspace = new LinkedList<>(); int wCapacity = capacity; boolean inProgress = true; while( inProgress ) { int greatestValue = -1; int greatestIndex = -1; for( int i = 0; i < in.length; ++i ) { int value = in[i]; if( value > Integer.MIN_VALUE && greatestValue < value && value <= wCapacity ) { greatestValue = value; greatestIndex = i; } } if( greatestIndex >= 0 ) { workspace.add( greatestIndex ); in[greatestIndex] = Integer.MIN_VALUE; wCapacity -= greatestValue; } else if( workspace.isEmpty()) { inProgress = false; } else { int[] ws = new int[workspace.size()]; for( int i = 0; i < workspace.size(); ++i ) { ws[i] = workspace.get(i).intValue(); } indices.add( ws ); workspace = new LinkedList<>(); wCapacity = capacity; } } } static void print( int[] values, List< int[] > indices ) { int r = 0; for( int[] t : indices ) { String items = ""; int sum = 0; for( int index : t ) { int value = values[index]; if( ! items.isEmpty()) { items += ", "; } items += index + ":" + value; sum += value; } System.out.println( "S" + ++r + " (" + sum + ") : " + items ); } } public static void main( String[] args ) { int[] values = { 9, 18, 7, 8, 4, 9, 11, 15, 3, 8 }; List< int[] > indices = new LinkedList<>(); knapsack( 20, values, indices ); print( values, indices ); } }
结果：
S1 (18) : 1:18 S2 (19) : 7:15, 4:4 S3 (20) : 6:11, 0:9 S4 (20) : 5:9, 3:8, 8:3 S5 (15) : 9:8, 2:7