Java: grupowanie liczb całkowitych

Question

Zastanawiam się, jaki jest najlepszy sposób, aby zestawić podany zestaw liczb pod względem czasu przetwarzania. przedmioty zabrać ze sobą: 9, 18, 7, 8, 4, 9, 11, 15, 3, 8, (pozycja 1 ma czas przetwarzania 9 pkt 2 ma czas przetwarzania 18, etc.)

Jeśli limit czasu przetwarzania wsadowego jest ustawiony do powiedzenia 20, następnie możliwe grupowanie przedmiotów w partie to: {1, 3, 5} {2} {4, 6} {8, 9} {7, 10} (grupa 1 9 + 7 + 4 = 20) itp więc 5 partie przedmiotów zostały wykonane w którym zawartość < = 20.

Idealnie ma to skontaktować je za mniej grupy, jak to możliwe. Sprawa jest powyżej minimum 5 grup z limitem zawartości 20 ...

Dzięki

Answer 1

Jeśli limit czasu przetwarzania wsadowego jest ustawiony na 20, powiedzieć ...

Tak Zakładam, że nie ma elementu dłuższego niż limit czasu przetwarzania wsadowego. Oto moje podejście:

• Najpierw posortuj elementy. Następnie uzyskaj 2 wskaźniki dla listy, jedna jest na indeks 0 (left-pointer), a druga na ostatnim indeksie (right-pointer).
• Przejmij element wskaźnika prawego i dodaj go do podlisty. Zrób element lewej strzałki i dodaj go do tej samej podlisty. Jeśli suma elementów na liście podrzędnej jest mniejsza niż limit, zaktualizuj lewą-wskaźnik (ustaw dla następnego elementu) i spróbuj dodać. Kontynuuj ten proces, dopóki nie zostanie wypełniona podlista .
• Następnie zacznij wypełniać następną podlistę. Zużyj wszystkie elementy do konstruowania podlist.

Implementacja w 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. 
} 

Drukowanie grupy:

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

wyjściowa: (Każda linia oznacza grupę numerów)

18 
15 3 
11 4 
9 7 
9 8 
8 

Answer 2

1. Weź największy ze zbioru W i umieścić w nowym zbiorze S. (pkt 2, wartość 18)
2. spróbować znaleźć największy przedmiot o wartości < = (20 - 18): brak dodaj S do listy zestawów.
3. Jeżeli nie będzie pusta przejść do kroku 1

Powtórzenia:

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

Kod:

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

Rezultatem

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