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，...

所以我假設沒有大於批處理時間限制的元素。這是我的方法：

• 首先對項目進行排序。然後獲取列表的兩個指針，一個是 索引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<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 

Answer 2

1. 輪流來自中設置的最大，裝入一個新的集合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