Come trovare un sottoinsieme di dimensioni k tale che la distanza minima tra i valori sia massima

Question

Come trovare un sottoinsieme di dimensioni k tale che la distanza minima tra i valori sia massima

#1 da (-1 voti)

0

Supponiamo che abbia un array ordinato che contiene n interi.
Come trovo un sottoinsieme di dimensioni k tale che la distanza minima tra tutte le coppie di interi nel sottoinsieme sia massimizzata, cioè che siano alla massima distanza.

esempio: array a[]={1,2,6,7,10} e k=3 ,
subset = {1,6,10} , la distanza minima è 4 tra 10 e 6.
Sottoinsiemi errati:
{1,7,10} , distanza minima è 3 e {1,2,6} , la distanza minima è 1

Il mio primo pensiero è stato ottenere tutte le combinazioni nella dimensione di k, quindi calcolare la distanza di ciascuna di esse. Ma la complessità del tempo sarebbe O (n!), E l'intervistatore non gli piace. La programmazione dinamica è il suggerimento che mi ha dato, ma non ne ho ancora idea.

Ha suggerito di poter iniziare da un [0], trovare un [0] + x = Y anche nell'array ... e poi Y + x e così su k-1 volte, anche l'elemento kth sarà un [n-1], ma non sono riuscito a prenderlo. Non so perché ci deve essere un x , come nell'esempio sopra, la risposta corretta è {1,6,10}, la distanza tra 1 e 6 è 5, ed è 4 tra 6 e 10, allora cosa dovrebbe x essere?

java dynamic-programming

posta Ona 15.12.2015 - 03:03

fonte

1 risposta

Leggi altre domande sui tag java dynamic-programming

Forzatura aggiornamento della cache In UML è corretto avere una classe di associazione con una composizione o una relazione di aggregazione?

score -1 · Answer 1

Per alcuni elenchi e dimensioni date, potrebbe avere molte risposte corrette.

Proverò un algoritmo avido invece del backtracking: data una sotto-selezione, se si vuole estenderla ad un elemento extra, si deve semplicemente selezionare il nuovo, poiché il massimo delle distanze minime può solo diminuire come il numero di elementi aumenta. Complessità: O (k * n * n), che è migliore di O (n!).

Se ignori casi speciali (dimensioni > list.size, ecc.):

List<Int> maxmin(List<Int> l, int size)
{
   Int head = l.subList(0, 1);
   List<Int> tail = l.subList(1, l.size());
   more(head, tail, size-1);
}

private List<Int> more(List<Int> selected, List<Int> available, int size)
{
   if(size == 0) return selected;
   else
   {
      int max = maxByMin(available, selected);
      selected.add(max);
      available.remove(max);
      return more(selected, available, size-1);
   }
}

private int maxByMin(List<Int> candidates, List<Int> elements)
{
   int maxMin = Integer.MIN_VALUE;
   int maxVal = candidates(0);

   for(int candidate : candidates)
   {
      int minDist = Integer.MAX_VALUE;

      for(int element : elements)
      {
         int dist = math.abs(candidate, element);
         if(dist < minDist)
         {
             minDist = dist;
         }
      }

      if(minDist > maxMin)
      {
         maxMin = minDist;
         maxVal = candidate;
      }
   }
   return candidate;
}

In Scala:

def maxmin(l: Seq[Int], size: Int): Seq[Int] =
{
  def more(selected: Seq[Int], reminder: Seq[Int], size: Int): Seq[Int] =
  {
     if(size == 0) selected
     else
     {
        val max = reminder.maxBy(x => selected.map(y => math.abs(y - x)).min)
        more(selected :+ max, reminder diff Seq(max), size-1)
     }
  }

  more(Seq(l.head), l.tail, size-1)
}

Non ho controllato il codice Java, ma quello di Scala sembra OK. Altrimenti, si prega di fornire un contro-esempio perché probabilmente significa che non ho capito il problema.