8

我想知道最好的方法是在处理时间方面对一组给定的数字进行批处理。Take items：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...

谢谢

4

2 回答 2

4

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

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

  • 首先对项目进行排序。然后获取列表的 2 个指针，一个位于索引 0（左指针），另一个位于最后一个索引（右指针）。
  • 获取右指针的元素并将其添加到子列表中。获取left-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
于 2012-11-28T20:08:25.320 回答
3
  1. 从 IN 集合中取出最大的并放入新的集合 S。（项目 2，值 18）
  2. 尝试找到值 <= (20 - 18) 的最大项目：无，将 S 添加到集合列表中。
  3. 如果 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
于 2012-11-28T20:14:47.070 回答