Java: số nguyên batching

Question

Tôi đã tự hỏi cách tốt nhất là xếp hàng loạt tập hợp số đã cho theo thời gian xử lý. mục thực hiện: 9, 18, 7, 8, 4, 9, 11, 15, 3, 8, (mục 1 có thời gian xử lý của 9, mục 2 có thời gian xử lý là 18, vv)

Nếu thời gian xử lý giới hạn hàng loạt được thiết lập để nói 20, sau đó một nhóm có thể có của các mục thành các lô sẽ là: {1, 3, 5} {2} {4, 6} {8, 9} {7, 10} (nhóm 1 là 9 + 7 + 4 = 20) v.v ... vì vậy 5 lô mục đã được thực hiện trong đó nội dung là < = 20.

Lý tưởng nhất là tôi muốn sắp xếp chúng thành ít hơn nhóm càng tốt. trường hợp trên là tối thiểu là 5 nhóm với một giới hạn nội dung của 20 ...

Cảm ơn

Answer 1

Nếu thời gian xử lý giới hạn hàng loạt được thiết lập để nói 20, ...

Vì vậy, Tôi giả sử rằng không có phần tử nào lớn hơn giới hạn thời gian xử lý theo lô. Đây là cách tiếp cận của tôi:

• Thứ nhất sắp xếp các mục. Sau đó nhận được 2 con trỏ cho danh sách, một con trỏ nằm ở số chỉ số 0 (con trỏ bên trái) và một con trỏ khác ở chỉ mục cuối cùng (con trỏ phải).
• Lấy phần tử của con trỏ chuột phải và thêm nó vào danh sách con. Lấy phần tử của con trỏ trái và thêm nó vào cùng một danh sách con. Nếu tổng của các phần tử trong danh sách con nhỏ hơn giới hạn, hãy cập nhật con trỏ trái (đặt thành phần tử tiếp theo) và thử thêm nó. Tiếp tục quá trình này cho đến khi một danh sách phụ được điền.
• Sau đó bắt đầu điền vào danh sách phụ tiếp theo. Sử dụng tất cả các phần tử để tạo danh sách phụ.

thực hiện trong 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. 
} 

In các nhóm:

for (ArrayList<Integer> subList : list) 
{ 
    for (int i : subList) 
     System.out.print(i + " "); 
    System.out.println(); 
} 

Output: (Mỗi dòng biểu thị một nhóm các số)

18 
15 3 
11 4 
9 7 
9 8 
8 

Answer 2

1. Hãy lớn nhất từ ​​tập IN và đưa vào một bộ mới S. (mục 2, giá trị 18)
2. Cố gắng tìm ra mục lớn nhất với giá trị < = (20-18): none, thêm S đến một danh sách các thiết lập.
3. nếu TRÊN không phải là trống rỗng GOTO 1

Iterations:

      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: _, _, _, _, _, _, _, _, _, _ 

Mã:

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); 
    } 
} 

Kết quả:

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