Podziel tablicę w równym rozmiarze, tak aby wartość podanej funkcji była minimalna.

Question

Natrafiłem na następujące stwierdzenie problemu.

Masz listę liczb naturalnych wielkości N i trzeba rozpowszechniać wartości w dwóch listach A i B wielkości N/2, tak że do kwadratu sumy A elementów jest najbliższy możliwy do mnożenia B elementy.

przykład: uznaje wyliczenia 7 11 1 9 10 3 5 13 9 12.
Optymalny rozkład jest:
Lista A: 5 9 9 12 13
Zestawienie B: 1 3 7 10 11
co prowadzi do różnicy abs ((5 + 9 + 9 + 12 + 13)^2 - (1 * 3 * 7 * 10 * 11)) = 6
Twój program powinien wyprowadzić 6, co jest minimum Różnica, którą można osiągnąć.

Co próbowałem:

Próbowałem Greedy podejście w celu rozwiązania tego problemu. Wziąłem dwie zmienne: sum i mul. Teraz zacząłem pobierać elementy z podanego zestawu jeden po drugim i próbowałem dodawać go zarówno do zmiennych, jak i do obliczonego bieżącego kwadratu sumy i mnożenia. Teraz sfinalizuj element w jednym z dwóch zestawów, tak aby kombinacja zapewniała minimalną możliwą wartość.

Ale to podejście nie działa w danym przykładzie itselt. Nie wiem, jakie podejście można tu zastosować.

Jestem nie z prośbą o podanie dokładnego kodu rozwiązania. Wszelkie możliwe podejście i powód, dla którego działa, byłoby w porządku.

EDIT:

Źródło: CodinGame, Community puzzle

Answer 1

Nie jestem pewien, czy istnieje jakikolwiek dokładnego rozwiązania w czasie wielomianowym. Ale możesz spróbować podejścia opartego na wyżarzaniu symulowanym.

Moje podejście byłoby:

1. Initialize Lišta i listB do stanu losowej
2. z prawdopodobieństwem p run chciwy kroku, inaczej uruchomić losową krok
3. Śledzić państwa i odpowiadający błąd (z HashMap)

Chciwy krok: Znajdź jeden element, który możesz przemieszczać się między listą, która optymalizuje błąd.

Losowy krok: Wybierz losowy element z jednego z tych dwóch zestawów i oblicz błąd. Jeśli błąd jest lepszy, zatrzymaj go. W przeciwnym razie z prawdopodobieństwem q zachowaj to.

W jednym z tych dwóch kroków upewnij się, że nowy stan nie jest już zbadany (lub przynajmniej go zniechęcić).

Ustawienie p na małą wartość (< 0,1) i q może zależeć od różnicy błędów.

Answer 2

Wypróbuj to:

import java.util.Arrays; 

public class Test { 

    public static void main(String [] args){ 
     int [] arr = {7, 11, 1, 9, 10, 3, 5, 13, 9, 12}; 
     int [][] res = combinations(5, arr); 
     int N = Arrays.stream(arr).reduce(1, (a, b) -> a * b); 
     int min = Integer.MAX_VALUE; 
     int [] opt = new int [5]; 
     for (int [] i : res){ 
      int k = (int) Math.abs(Math.pow(Arrays.stream(i).sum(), 2) - N/(Arrays.stream(i).reduce(1, (a, b) -> a * b))); 
      if(k < min){ 
       min = k; 
       opt = i; 
      } 
     } 
     Arrays.sort(opt); 
     System.out.println("minimum difference is "+ min + " with the subset containing this elements " + Arrays.toString(opt)); 
    } 

    // returns all k-sized subsets of a n-sized set 
    public static int[][] combinations(int k, int[] set) { 
     int c = (int) binomial(set.length, k); 
     int[][] res = new int[c][Math.max(0, k)]; 
     int[] ind = k < 0 ? null : new int[k]; 
     for (int i = 0; i < k; ++i) { 
      ind[i] = i; 
     } 
     for (int i = 0; i < c; ++i) { 
      for (int j = 0; j < k; ++j) { 
       res[i][j] = set[ind[j]]; 
      } 
      int x = ind.length - 1; 
      boolean loop; 
      do { 
       loop = false; 
       ind[x] = ind[x] + 1; 
       if (ind[x] > set.length - (k - x)) { 
        --x; 
        loop = x >= 0; 
       } else { 
        for (int x1 = x + 1; x1 < ind.length; ++x1) { 
         ind[x1] = ind[x1 - 1] + 1; 
        } 
       } 
      } while (loop); 
     } 
     return res; 
    } 
    // returns n choose k; 
    // there are n choose k combinations without repetition and without observance of the sequence 
    // 
    private static long binomial(int n, int k) { 
     if (k < 0 || k > n) return 0; 
     if (k > n - k) { 
      k = n - k; 
     } 
     long c = 1; 
     for (int i = 1; i < k+1; ++i) { 
      c = c * (n - (k - i)); 
      c = c/i; 
     } 
     return c; 
    } 
} 

Kod wzięty z this stackoverflow answer również przyjrzeć this wikipedia artykuł o kombinacjach.