8

処理時間の観点から、特定の数値のセットをバッチ処理するのが最善の方法であるかどうか疑問に思いました。アイテムを取る:(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。

理想的には、それらをできるだけ少ないグループに分類したいと思います。上記の場合は、コンテンツ制限が20の最低5つのグループです...

ありがとう

4

2 に答える 2

4

バッチ処理の制限時間が20に設定されている場合、...

したがって、バッチ処理の制限時間を超える要素はないと仮定します。これが私のアプローチです：

  • まず、アイテムを並べ替えます。次に、リストの2つのポインターを取得します。1つはインデックス0（左ポインター）にあり、もう1つは最後のインデックス（右ポインター）にあります。
  • 右ポインタの要素を取得して、サブリストに追加します。左ポインタの要素を取得し、同じサブリストに追加します。サブリスト内の要素の合計が制限未満の場合は、左ポインターを更新して（次の要素に設定）、追加してみてください。サブリストがいっぱいになるまでこのプロセスを続けます。
  • 次に、次のサブリストの入力を開始します。サブリストを作成するためにすべての要素を消費します。

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が空でない場合GOTO1

反復：

                            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 に答える