1005. Stone Pile

You have a number of stones with known weights W1, …, Wn. Write a program that will rearrange the stones into two piles such that weight difference between the piles is minimal.

Input

Input contains the number of stones N (1 = N = 20) and weights of the stones W1, …, Wn (integers, 1 = Wi = 100000) delimited by white spaces.

Output

Your program should output a number representing the minimal possible weight difference between stone piles.

Sample

Input

5

5 8 13 27 14

Output

3

http://acm.timus.ru/problem.aspx?space=1&num=1005

Solución:

Este es un conocido problema de categoria NP-completo, es decir no existe una solucion de orden polinomica que podamos aplicara para hallar la solucion. Por tanto realizaremos una busqueda exhaustiva de todas las formas en que podemos dividir los pesos de las piedras en dos grupos, y asi ir buscando la diferencia minima de esos 2 grupos.

A cada elemento, le podemos asignar un 1 para indicar que se va añadir al primer grupo, y 0 para el segundo grupo:

14  27 13 8 5     Grupo1     Grupo2      

 0   0  0 0 0  :      67          0

 0   0  0 0 1  :       5         62

 0   0  0 1 0  :       8         59

 0   0  0 1 1  :      13         54

y asi sucesivamente.   Se observa que cada  distribucion se puede representar como un numero binario y ademas de que cada distribucion es igual a la anterior luego de añadir un bit.

Podemos ir calculando el peso de cada grupo al mismo tiempo que añadimos un bit a la distribucion anterior:

Mientras no encontremos un bit 0

   Si el bit actual es 1, indica que el elemento actual esta en 

   el grupo 1, pero luego de añadirle el bit del acarreo este se 

   vuelve 0, por tanto quitamos este elemento del grupo 1 y lo   

   añadimos al grupo2. 

Cuando encontramos el bit 0 ( este elemento pertenece al grupo 2 ), lo convertimos en un 1 y quitamos este elemento del grupo2 y lo añadimos al grupo1. 


Es importante hacer notar que este algoritmo tiene un coste amortizado de 2n, donde n es el numero de distribuciones posibles.

public class Problema1005 
{
   public static void main( String args[] ) throws Exception
   {
      int pila1 = 0, pila2 = 0;
      int numPiedras = sig();

      // Nos saltamos el simbolo de fin de liena
      System.in.read();
  
      int[] pesoPiedras = new int[ numPiedras ];
  
      for( int i = 0; i < numPiedras; i ++ )
         pila2 += pesoPiedras[ i ] = sig();
  
      // Representaremos cada bit con su correspondiente valor 
      // booleano.  1 -> True   0 -> False
      // Inicialmente todos los bits estan en 0, por tanto
      // todos los elementos estan en el grupo2
      boolean[] distribucion = new boolean[ numPiedras ];

      int cantDistrib = (int)Math.pow( 2, numPiedras ) - 1;
      int minDiferencia = 2000000, i, dif;
  
      while( cantDistrib -- > 0 )
      {
         i = 0;
   
         // Cada vez que encontremos un 1 lo convertimos en 0 y pasamos
         // este elemento del grupo 1 al grupo2
         for( i = 0; i < numPiedras && distribucion[ i ]; i ++ )
         {
            pila1 -= pesoPiedras[ i ];
            pila2 += pesoPiedras[ i ];
    
            distribucion[ i ] = false;
         }
   
         // El bit actual es un 1, por tanto pasamos el elemento del grupo
         // 2 al grupo 1.
         pila1 += pesoPiedras[ i ];
         pila2 -= pesoPiedras[ i ];
         distribucion[ i ] = true;
   
         // Verificamos si la diferencia es menor que todas las encontradas
         // hasta ahora
         dif = Math.abs( pila1 - pila2 );
   
         if( dif < minDiferencia )
            minDiferencia = dif;
      }
  
      System.out.println( minDiferencia );  
   }
 
   public static int sig() throws Exception
   {
      int val = System.in.read() - 48;
      int car = System.in.read();
  
      while( car > 47 && car < 58 )
      {
         val = 10 * val + car - 48;
         car = System.in.read();
      }
  
      return val;
   }
}