Bueno, cuando compro regalos para mis dos esposas, quiero que se sientan igualmente importantes para mí, pero es difícil ir de compras con presupuestos fijos. En cambio, compro un montón de cosas y las divido en dos grupos con el mismo valor posible. Luego compro un montón de bombones para arreglar el resto.

Pero no quiero hacer todo el trabajo duro cuando mi computadora puede hacerlo. Y tú tampoco. Así que resuelva este problema para que la próxima vez que necesite dividir los regalos entre sus esposas, sepa que sería fácil.

Entrada

1 conjunto de elementos (N * 2) donde N * 2 se especifica en la primera línea.
Los elementos de la matriz en la siguiente línea.

Salida

2 conjuntos de N elementos cada uno de manera que: La
diferencia de (Suma de elementos del conjunto 1) y (Suma de elementos del conjunto 2) sea lo más cercana posible a 0.

Ejemplo

Entrada

4
1 2 3 4 

Salida

1 4
2 3
diff=0

Descargo de responsabilidad : no tengo dos esposas. Pero cuando me siento mal, imagino tener dos esposas. Y de repente, estoy agradecido y feliz de tener solo uno. :RE

Java

Intentando resolver este problema en dos fases:

1. Cree dos listas de igual tamaño agregando la más grande restante a la lista más pequeña actualmente y la siguiente a la otra. Repetir.
2. Identifique los elementos de ambas listas que se pueden cambiar para reducir la diferencia de valor.

Entrada como

8
1 2 3 4 5 6 7 8

ya está resuelto después de la fase 1 como p. ej.

2 3 5 8
1 4 6 7
diff=0

y entrada como

6
1 4 5 6 7 8

necesitará ambas fases para que

1 5 8
4 6 7
diff=3

(después de la fase uno) se convierte en el resultado de

1 6 8
4 5 7
diff=1

Si bien puedo garantizar que este intento siempre proporcionará una solución, no puedo demostrar que se encuentre una solución óptima en todos los casos. Sin embargo, con la restricción de listas de igual tamaño, parece bastante realista que no queden casos de esquina. Prueba que estoy equivocado ;-)

Programa en ideone.com

import java.util.*;

/**
 * Created to solve http://codegolf.stackexchange.com/q/23461/16293 .
 */
public class EqualSums {

    public static void main(String[] args) {
        final Scanner s = new Scanner(System.in);
        // Read number of elements to divide
        final int count = s.nextInt();
        if (count % 2 == 1) {
            throw new IllegalStateException(count + " can not be divided by 2. Consider adding a 0 value.");
        }
        // Read the elements to divide
        final SortedList valueStack = new SortedList(count);
        for (int i = 0; i < count; i++) {
            valueStack.add(s.nextLong());
        }

        final SortedList targetOne = new SortedList(count / 2);
        final SortedList targetTwo = new SortedList(count / 2);
        // Divide elements into two groups
        addInPairs(targetOne, targetTwo, valueStack);
        // Try to ensure groups have equal value
        retaliate(targetOne, targetTwo);

        // Output result
        System.out.println(targetOne);
        System.out.println(targetTwo);
        System.out.println("diff=" + Math.abs(targetOne.getSum() - targetTwo.getSum()));
    }

    private static void addInPairs(SortedList targetOne, SortedList targetTwo, SortedList valueStack) {
        SortedList smallerTarget = targetOne;
        SortedList biggerTarget = targetTwo;
        while (!valueStack.isEmpty()) {
            // Add biggest remaining value to small target
            smallerTarget.add(valueStack.removeLast());

            // Add second biggest remaining value to big target
            biggerTarget.add(valueStack.removeLast());

            // Flip targets if roles have changed
            if (smallerTarget.getSum() > biggerTarget.getSum()) {
                final SortedList temp = smallerTarget;
                smallerTarget = biggerTarget;
                biggerTarget = temp;
            }
        }

    }

    private static void retaliate(SortedList targetOne, SortedList targetTwo) {
        long difference;
        boolean changed;
        outer:
        do {
            difference = Math.abs(targetOne.getSum() - targetTwo.getSum());
            if (difference == 0) {
                return;
            }
            changed = false;
            // Try to find two values, that reduce the difference by changing them between targets
            for (Long valueOne : targetOne) {
                for (Long valueTwo : targetTwo) {
                    final Long tempOne = targetOne.getSum() + valueTwo - valueOne;
                    final Long tempTwo = targetTwo.getSum() - valueTwo + valueOne;
                    if (Math.abs(tempOne - tempTwo) < difference) {
                        targetOne.remove(valueOne);
                        targetTwo.add(valueOne);
                        targetTwo.remove(valueTwo);
                        targetOne.add(valueTwo);
                        changed = true;
                        continue outer;
                    }
                }
            }
        } while (changed);
    }

    public static class SortedList extends AbstractList<Long> {

        private final ArrayList<Long> list;
        private long sum = 0;

        public SortedList(int count) {
            list = new ArrayList<>(count);
        }

        // the next functions access list-field directly
        @Override
        public Long get(int index) {
            return list.get(index);
        }

        @Override
        public boolean add(final Long t) {
            final int i = Collections.binarySearch(list, t);
            if (i < 0) {
                // No equal element present
                list.add(-i - 1, t);
            } else {
                list.add(afterLastEqual(i, t), t);
            }
            sum += t;
            return true;
        }

        @Override
        public Long remove(int index) {
            final Long old = list.remove(index);
            sum -= old;
            return old;
        }

        @Override
        public int size() {
            return list.size();
        }

        // the next functions access list-field only through the functions above this point
        // to ensure the sum is well kept

        public long getSum() {
            return sum;
        }

        private int afterLastEqual(final int start, Object o) {
            int found = start;
            while (found < size() && o.equals(get(found))) {
                found++;
            }
            return found;
        }

        private int beforeFirstEqual(final int start, final Object o) {
            int found = start;
            while (found >= 0 && o.equals(get(found))) {
                found--;
            }
            return found;
        }

        @Override
        public int indexOf(Object o) {
            try {
                final int i = Collections.binarySearch(this, (Long) o);
                if (i >= 0) {
                    return beforeFirstEqual(i, o) + 1;
                }
            } catch (ClassCastException e) {
                // Object was not instance of Long
            }
            return -1;
        }

        @Override
        public int lastIndexOf(Object o) {
            try {
                final int i = Collections.binarySearch(this, (Long) o);
                if (i >= 0) {
                    return afterLastEqual(i, o) - 1;
                }
            } catch (ClassCastException e) {
                // Object was not instance of Long
            }
            return -1;
        }

        @Override
        public boolean remove(Object o) {
            if (o == null) {
                return false;
            }
            final int i = indexOf(o);
            if (i >= 0) {
                remove(i);
                return true;
            }
            return false;
        }

        public Long removeLast() {
            return remove(size() - 1);
        }

        public Long removeFirst() {
            return remove(0);
        }

        @Override
        public String toString() {
            Iterator<Long> it = iterator();
            if (!it.hasNext()) {
                return "";
            }

            StringBuilder sb = new StringBuilder();
            for (; ; ) {
                Long e = it.next();
                sb.append(e);
                if (!it.hasNext()) {
                    return sb.toString();
                }
                sb.append(' ');
            }
        }
    }
}

Brachylog 2

pᶠḍᵐ{+ᵐo-}ᵒh

Pruébalo en línea!

Este es un concurso de popularidad, pero eso no significa necesariamente que los idiomas de golf no encajen bien. (Realmente, debería haber respondido en Jelly porque las respuestas de Jelly tienden a obtener una cantidad desproporcionada de votos a favor por alguna razón, independientemente de quién los envíe o cuán golfizados estén, pero Brachylog es más legible).

Comenzamos tomando la lista de todas las permutaciones de la entrada ( pᶠ), y dividiendo cada ( ᵐ) en dos partes iguales ( ḍ; podríamos asignarle un subíndice si tuviera más de dos esposas por alguna razón). Luego ordenamos las permutaciones divididas ( {…}ᵒ) tomando la suma ( +) de cada ( ᵐ) mitad, tomando la diferencia absoluta (es decir o-, "diferencia ordenada") y usando esas diferencias para definir el orden de clasificación. El mejor resultado es el primero, por lo que tomamos el encabezado de la lista hpara obtener el resultado.

Mathematica

Formularios de entrada

La cadena de entrada debe tomarse a través de STDIN. assetsse refiere a las cantidades que se distribuirán entre las esposas (o gemelas). lengthes la cantidad de activos.

assets=ToExpression[Rest[s=StringSplit[input]]]
length=ToExpression[First[s]]

A los fines del presente, asumiremos que los activos consisten en los enteros del 1 al 20.

assets=Range[20];
length=Length[Range[20]]

Procesando

(* find all possible distributions to one wife; the other presumably gets the remaining assets *)
r=Subsets[assets,{length/2}];

(*order them according to the difference with respect to the total of half of the assets. 
Remove the first set of assets.  One wife will get these.*)
s=SortBy[r/.{{a__Integer}:> {{a},Abs[Tr[Range[20]/2]-Tr[{a}]]}},Last][[1]];

(*The other wife's assets will be the complement.  The difference is carried over from the sorting routine. *)
Grid[{{Grid[{s[[1]],Complement[assets,s[[1]]]}]},{"difference = "<>ToString[s[[2]]]}}]

¿Es injusta la distribución? Entonces, elige otro.

@The Constructor señala que la esposa 2 puede cuestionar el hecho de que la esposa 1 obtuvo todos los mejores activos. Entonces, lo siguiente produce todas las acciones "justas" (diferencia = diferencia más baja) para la esposa 1; la esposa 2 obtiene los activos restantes; el cero se refiere a la diferencia en activos para las esposas. Hay 5448 formas de distribuir activos ponderados del 1 al 20. Solo se muestran unas pocas líneas.

El formato es

s=SortBy[r/.{{a__Integer}:> {{a},Abs[Tr[Range[20]/2]-Tr[{a}]]}},Last];
z=Cases[s,{_List,x_}/;x==s[[1,2]]];
Short[z,10]
Length[z]

{{{1,2,3,4,5,16,17,18,19,20}, 0}, {{1,2,3,4,6,15,17,18,19,20}, 0}, {{1,2,3,4,7,14,17,18,19,20}, 0}, {{1,2,3,4,7,15,16,18,19,20 }, 0}, {{1,2,3,4,8,13,17,18,19,20}, 0}, {{1,2,3,4,8,14,16,18,19 , 20}, 0}, {{1,2,3,4,8,15,16,17,19,20}, 0}, {{1,2,3,4,9,12,17,18 , 19,20}, 0}, {{1,2,3,4,9,13,16,18,19,20}, 0}, {{1,2,3,4,9,14,15 , 18,19,20}, 0}, {{1,2,3,4,9,14,16,17,19,20}, 0}, {{1,2,3,4,9,15 , 16,17,18,20}, 0}, {{1,2,3,4,10,11,17,18,19,20}, 0}, {{1,2,3,4,10 , 12,16,18,19,20}, 0}, <<5420>>, {{5,6,7,8,9,11,13,14,15,17}, 0}, {{5 , 6,7,8,9,12,13,14,15,16}, 0}, {{5,6,7,8,10,11,12,13,14,19}, 0}, { {5,6,7,8,10,11,12,13,15,18}, 0}, {{5,6,7,8,10,11,12,13,16,17}, 0} , {{5,6,7,8,10,11,12,14,15,17}, 0}, {{5,6,7,8,10,11,13,14,15,16}, 0}, {{5,6,7,9,10,11,12,13,14,18}, 0}, {{5,6,7,9,10,11,12,13,15,17 }, 0}, {{5,6,7,9,10,11,12,14,15,16}, 0}, {{5,6,8,9,10,11,12,13,14 , 17}, 0}, {{5,6,8,9,10,11,12,13,15,16}, 0}, {{5,7,8,9,10,11,12,13,14,16}, 0}, {{6,7,8,9,10,11,12,13,14,15}, 0}}

5448

La presentación previa se puede encontrar entre las ediciones. Es mucho más ineficiente, confiando como lo hace Permutations.

J

Hay una hoja de trucos de todas las primitivas J en este enlace , en caso de que quiera seguirlo en casa. Recuerde: J generalmente se lee de derecha a izquierda, por lo que 3*2+1es 7, no 9. Cada verbo (J para función) es monádico, por delante f y, o diádico, por lo tanto, entre x f y.

N =: (". 1!:1 ] 1) % 2          NB. number of items per wife
S =: ". 1!:1 ] 1                NB. list of items to distribute

bins =: #: i. 2 ^ 2*N           NB. all binary strings of length 2n
even =: bins #~ N = +/"1 bins   NB. select those with row-sum 1

NB. all distributions of equal numbers of items to each wife
NB. resultant shape: a list of 2xN matrices
NB. this /. adverb is where all the magic happens, see below
dist =: even ]/."1 S

diff =: | -/"1 +/"1 dist        NB. difference in wives' values
idx  =: (i. <./) diff           NB. index of the lowest difference

1!:2&2 idx { dist               NB. print the winning distribution of items
1!:2&2 'diff=', idx { diff      NB. and the difference of that distribution

Notas y explicaciones:

• u/significa "doblar u", así que realice la operación binaria sobre cada elemento de la lista. Entonces, por ejemplo: +/significa Fold Plus o Sum ; <.es Menor de , entonces <./significa Plegar Menor de , o Mínimo .

• u"1significa "realizar uen celdas unidimensionales", es decir, en cada fila. Normalmente, los verbos en J son atómicos o se aplican a todo el argumento. Esto se aplica a ambos argumentos si el verbo se usa de forma diádica (con dos argumentos). Considera lo siguiente:

     i. 2 3        NB. just a 2x3 matrix of numbers
  0 1 2
  3 4 5
     +/   i. 2 3   NB. Sum the items
  3 5 7
     +/"1 i. 2 3   NB. Sum the items of each row
  3 12
  

• #:es un verbo que expande un número en su representación binaria. Cuando lo usa en una lista con más de un elemento, también alineará todos los números correctamente, de modo que #:i.2^nobtendrá cada cadena binaria de longitud n.

• /., Cuando se usa diádica, que se denomina clave . Utiliza los elementos de la lista en el lado izquierdo como claves y los del lado derecho como valores. Agrupa cada conjunto de valores que comparten una clave y luego realiza alguna operación en ellos.

  En el caso de ]/., la operación es solo el verbo de identidad, por lo que no está sucediendo nada completamente especial allí, pero el hecho de que /.dividirá la lista para nosotros es lo importante. Es por eso que creamos las listas binarias: para que para cada lista ( "1), podamos repartir los regalos para las esposas de todas las formas posibles.

• 1!:1]1y 1!:2&2son las operaciones de lectura y escritura, respectivamente. La 1!:nparte es el verbo y el otro número es el identificador de archivo. 1está dentro de la consola, 2está fuera de la consola y 3 4 5son stdin, stdout y stderr. También usamos ".cuando leemos para convertir las cadenas de entrada a números.

Clojure

(defn divide [n]
 (loop [lv [] rv [] d (reverse (sort n))]
  (if (empty? d)
   [lv rv]
   (if (> (reduce + lv) (reduce + rv))
     (if (>= (count lv ) (count rv))
       (recur lv (conj rv (first d)) (into [] (rest d)))
       (recur (conj lv (last d)) rv (pop d))) 
     (if (<= (count lv ) (count rv))
       (recur (conj lv (first d)) rv (into [] (rest d)) )
       (recur lv (conj rv (last d)) (pop d)))))))


 (defn display [[f s]]
   (println f)
   (println s)
   (println (str "Diff " (- (reduce + f) (reduce + s)))))

Prueba

 (->> 
 [5 1 89 36 2 -4 20 7]
 divide 
 display)


 =: [89 -4 1 2]
    [36 20 7 5]
    Diff 20

MATLAB

Aquí está mi solución:

%input array
presents=zeros(2,8);
presents(1,1)=8; %number of presents
presents(2,:)=[1 2 7 4 5 3 2 8]; %list of presents

%calculate the cumulative sum of all permutations
%its all about the gift values
how_many=presents(1,1);
options=perms(presents(2,:);
subtotals=cumsum(options,2);

%find the first index where the difference between the two parts is minimal
%makes both wives happy!!
[~, double_happiness] = min(abs(sum(presents(2,:))/2-subtotals(:,how_many/2)));

%create the present lists for Jennifer and Kate :)
for_jennifer=options(double_happiness,1:how_many/2)
for_kate=options(double_happiness,how_many/2+1:end)

Por ejemplo, la lista actual en mi código fuente da como resultado:

for_jennifer =

     8     2     5     1


for_kate =

     4     7     2     3

que es ambos 16.

Si juego mi código, que es menos divertido, obtengo 132 caracteres muy poco optimizados. Supera eso ;)

function f(p);o=perms(p(:,2));s=cumsum(o,2);[~,d]=min(abs(sum(p(:,2))/2-s(:,p(1,1)/2)));a={o(d,1:p(1,1)/2);o(d,p(1,1)/2+1:end)};a{:}

PHP

Advertencia: código muy sucio
Intenta todas las permutaciones posibles de la matriz de entrada.

Muestra de ideona para 4/1 2 3 4: http://ideone.com/gIi174

<?php
// Discard the first input line! It's useless :)
fgets(STDIN);
$numbers = explode(' ', rtrim(fgets(STDIN)));
$valuePerWife = array_sum($numbers) / 2;

// Taken from here: http://stackoverflow.com/a/13194803/603003
// Credits to dAngelov: http://stackoverflow.com/users/955185/dangelov
function pc_permute($items, $perms = array( )) {
    if (empty($items)) {
        $return = array($perms);
    }  else {
        $return = array();
        for ($i = count($items) - 1; $i >= 0; --$i) {
             $newitems = $items;
             $newperms = $perms;
         list($foo) = array_splice($newitems, $i, 1);
             array_unshift($newperms, $foo);
             $return = array_merge($return, pc_permute($newitems, $newperms));
         }
    }
    return $return;
}


foreach (pc_permute($numbers) as $permutation) {
    $sum = 0;
    $rest = [];

    for ($i=0; $i<count($permutation); $i++) {
        $sum += $permutation[$i];
        if ($sum == $valuePerWife) {
            $rest = array_slice($permutation, $i + 1);
            break;
        }
    }

    if (array_sum($rest) == $valuePerWife) {
        echo implode(' ', array_slice($permutation, 0, $i + 1)), "\n";
        echo implode(' ', array_slice($permutation, $i + 1)), "\n";
        echo 'diff=0';
        exit;
    }
}
exit('DIDNT FOUND ANY COMBINATION!');

Pitón:

import itertools as t
raw_input()
a=[int(i) for i in raw_input().split()]
a=list(t.permutations(a))
b=len(a[0])/2
c=[(d[b:],d[:b]) for d in a]
d=[abs(sum(d[b:])-sum(d[:b])) for d in a]
e=zip(d,c)
e.sort()
print " ".join([str(i) for i in e[0][1][0]])
print " ".join([str(i) for i in e[0][1][1]])
print "diff",e[0][0]

o un poco golfificado:

import itertools as t
b=int(raw_input())/2
e=[(abs(sum(d[b:])-sum(d[:b])),(d[b:],d[:b])) for d in t.permutations([int(i) for i in raw_input().split()])]
e.sort()
f=e[0]
g=f[1]
print " ".join([str(i) for i in g[0]]),"\n"," ".join([str(i) for i in g[1]]),"\n","diff=",f[0]

O incluso más golfificado, ya que la mitad de las líneas es solo maquillaje. (suponiendo que pueda volcar la matriz interna sin procesar, ya que esto no se especifica en la operación) Puede dejar de lado el print(por ejemplo) el shell interactivo y agregar un [::-1](al final, después [0]) si realmente desea La diferencia es la última.

import itertools as t
b=int(raw_input())/2
print sorted([(abs(sum(d[b:])-sum(d[:b])),(d[b:],d[:b])) for d in t.permutations([int(i) for i in raw_input().split()])])[0]

(resultados en (0, ((1, 2, 7, 8), (3, 4, 5, 6))))

Esto, sin embargo, es solo la fuerza bruta de todas las combinaciones posibles, y no debe considerarse remotamente eficiente. Sin embargo, si la lista tiene igual longitud, esto también funcionaría (en matrices grandes):

raw_input()
a,b=[],[]
for i in sorted([int(i) for i in raw_input().split()])[::-1]:
    b.append(i)
    if sum(b)>sum(a): b,a=a,b
print a,b,abs(sum(b)-sum(a))

Con el código debajo de esto, por ejemplo, se ejecuta con apenas una diferencia: 500k con un valor máximo de 10 ^ 10 no es mucho, por así decirlo. Esto también es mucho más rápido: donde el otro código probablemente no terminaría en menos de un año (y eso es muy optimista), esto se ejecuta en aproximadamente medio segundo, a pesar de que su kilometraje puede variar.

def raw_input():
    import random
    return " ".join([str(random.randint(1,10**10)) for _ in range(10000)])

raw_input()
a,b=[],[]
for i in sorted([int(i) for i in raw_input().split()])[::-1]:
    b.append(i)
    if sum(b)>sum(a): b,a=a,b
print a,b,abs(sum(b)-sum(a))

Haskell alfabetizado

> import Data.List
> import Data.Function

Hice uso de la lista mónada para dividirlo.

> divide []=return ([], [])
> divide (x:xs)=do
>   (w1, w2) <- divide xs
>   [(x:w1, w2), (w1, x:w2)]

Luego hacemos un evaluador.

> rating (w1, w2)=abs $ (sum w1) - (sum w2)

Y luego una función que minimizará la diferencia.

> best = minimumBy (compare `on` rating) . filter (\(x,y)->length x == length y)

Y algo que los combina a todos.

> bestDivison=best . divide

Luego un analizador.

> parse::String->[Int]
> parse=fmap read . words

Y un formateador de salida.

> output (w1,w2)=unlines [unwords (map show w1)
>                        , unwords ( map show w2)
>                        , "diff="++(show $ abs $ (sum w1) - (sum w2))]

Y ahora el programa

> main = do
>   getLine --Ignored, I don't need the arrays length
>   input <- fmap parse getLine
>   putStrLn "" --For readability
>   putStrLn $ output $ bestDivison input

Ejemplo:

λ <*Main>: main
8
5 1 89 36 2 -4 20 7

5 36 20 7
1 89 2 -4
diff=20