Cóż, kiedy kupuję prezenty dla moich dwóch żon, chcę, aby poczuły się dla mnie równie ważne, ale ciężko jest robić zakupy z ustalonymi budżetami. Zamiast tego kupuję kilka rzeczy i dzielę je na dwie grupy o możliwie równej wartości. Następnie kupuję kilka czekoladek, aby naprawić resztę.

Ale nie chcę tego robić, gdy mój komputer może to zrobić. I ty też nie. Rozwiąż ten problem, aby następnym razem, gdy będziesz musiał podzielić prezenty między swoje żony, wiesz, że będzie to łatwe.

Wejście

1 tablica elementów (N * 2), w których N * 2 jest określony w pierwszym wierszu.
Elementy tablicy w następującym wierszu.

Wynik

2 tablice N elementów, z których każda:
Różnica (Suma elementów tablicy 1) i (Suma elementów tablicy 2) jest jak najbliższa zeru.

Przykład

Wejście

4
1 2 3 4 

Wynik

1 4
2 3
diff=0

Oświadczenie : Nie mam dwóch żon. Ale kiedy czuję się źle, wyobrażam sobie, że mam dwie żony. I nagle jestem wdzięczny i szczęśliwy, że mam tylko jeden. :RE

Jawa

Próbowanie rozwiązania tego problemu w dwóch fazach:

1. Zbuduj dwie jednakowej wielkości listy, dodając pozostałe największe do obecnie mniejszej listy, a następne obok drugiej. Powtarzać.
2. Zidentyfikuj elementy z obu list, które można przełączać, aby zmniejszyć różnicę wartości

Dane wejściowe jak

8
1 2 3 4 5 6 7 8

jest już rozwiązany po fazie 1 jak np

2 3 5 8
1 4 6 7
diff=0

i dane wejściowe jak

6
1 4 5 6 7 8

będą potrzebować obu faz, aby

1 5 8
4 6 7
diff=3

(po pierwszej fazie) staje się wynikiem

1 6 8
4 5 7
diff=1

Chociaż mogę zagwarantować, że ta próba zawsze zapewni rozwiązanie, nie mogę udowodnić, że we wszystkich przypadkach można znaleźć optymalne rozwiązanie. Jednak przy ograniczeniu list o takiej samej wielkości wydaje się całkiem realistyczne, że nie pozostały żadne narożne skrzynki. Udowodnij, że się mylę ;-)

Program na 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

Wypróbuj online!

To konkurs popularności, ale to niekoniecznie oznacza, że ​​języki gry w golfa są źle dopasowane. (Naprawdę, powinienem był odpowiedzieć w Jelly, ponieważ odpowiedzi Jelly mają tendencję do otrzymywania nieproporcjonalnej liczby głosów poparcia z jakiegoś powodu, niezależnie od tego, kto je przesyła lub jak są golfa, ale Brachylog jest bardziej czytelny.)

Zaczynamy od pobrania listy wszystkich permutacji wejścia ( pᶠ) i podzielenia każdego ( ᵐ) na dwie równe części ( ḍ; moglibyśmy dać indeks dolny, jeśli z jakiegoś powodu masz więcej niż dwie żony). Następnie porządkujemy podzielone permutacje ( {…}ᵒ), biorąc sumę ( +) każdej ( ᵐ) połowy, biorąc różnicę bezwzględną (tj. o-„Różnicę uporządkowaną”) i wykorzystując te różnice do zdefiniowania porządku sortowania. Najlepszy wynik jest pierwszy, więc bierzemy na czele listy, haby uzyskać wynik.

Matematyka

Formularze wejściowe

Ciąg wejściowy należy pobrać przez STDIN. assetsodnosi się do kwot, które zostaną rozdzielone między żony (lub bliźnięta). lengthto liczba aktywów.

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

Dla obecnych celów założymy, że aktywa składają się z liczb całkowitych od 1 do 20.

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

Przetwarzanie

(* 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]]]}}]

Czy dystrybucja jest niesprawiedliwa? Wybierz inny.

@ Konstruktor zauważa, że ​​żona 2 może zakwestionować fakt, że żona 1 ma wszystkie najlepsze aktywa. Tak więc poniższe dają wszystkie „sprawiedliwe” (różnica = najniższa różnica) akcje dla żony 1; żona 2 otrzymuje pozostałe aktywa; zero odnosi się do różnicy aktywów dla żon. Istnieje 5448 sposobów dystrybucji aktywów o wadze od 1 do 20. Wyświetlanych jest tylko kilka wierszy.

Format to

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

Wcześniejsze przesłanie można znaleźć wśród edycji. Jest o wiele bardziej nieefektywny, opierając się na nim Permutations.

jot

Pod tym linkiem znajduje się ściągawka wszystkich prymitywów J , na wypadek gdybyś chciał śledzić w domu. Pamiętaj: J jest ogólnie odczytywany od prawej do lewej, czyli 3*2+17, a nie 9. Każdy czasownik (J dla funkcji) jest albo monadyczny, czyli z przodu podobny f y, lub dyadyczny, więc pomiędzy podobnymi 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

Uwagi i objaśnienia:

• u/oznacza „złóż u”, więc wykonaj operację binarną nad każdym elementem na liście. Na przykład: +/oznacza Fold Plus lub Sum ; <.jest mniejszy , więc <./oznacza Krotnie mniejszy lub Minimalny .

• u"1oznacza „działaj una komórkach 1-wymiarowych”, tj. w każdym rzędzie. Zwykle czasowniki w J są atomowe lub odnoszą się do całego argumentu. Odnosi się to do obu argumentów, jeśli czasownik jest używany dyadycznie (z dwoma argumentami). Rozważ następujące:

     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
  

• #:to czasownik, który rozwija liczbę do reprezentacji binarnej. Kiedy użyjesz go na liście zawierającej więcej niż jeden element, spowoduje to również prawidłowe wyrównanie wszystkich liczb, dzięki czemu #:i.2^notrzymasz każdy ciąg binarny o długości n.

• /., gdy jest stosowany stopniowo, nazywa się Kluczem . Wykorzystuje elementy listy po lewej stronie jako klucze, a te po prawej stronie jako wartości. Grupuje razem każdy zestaw wartości, które mają wspólny klucz, a następnie wykonuje na nich pewne operacje.

  W przypadku ]/.operacji jest to tylko czasownik tożsamości, więc nie dzieje się tam nic specjalnego, ale fakt, że /.podzielimy listę dla nas, jest ważny. Dlatego tworzymy listy binarne: aby dla każdej listy ( "1) można było podzielić prezenty dla żon na wszystkie możliwe sposoby.

• 1!:1]1i 1!:2&2są odpowiednio operacjami wczytywania i zapisywania. 1!:nCzęścią jest przechodni, a druga liczba to uchwyt pliku. 1jest w konsoli, 2jest w konsoli, i 3 4 5są stdin, stdout i stderr. Używamy również ".podczas czytania, aby przekonwertować ciągi wejściowe na liczby.

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

Test

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


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

MATLAB

Oto moje rozwiązanie:

%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)

Na przykład obecna lista w moim kodzie źródłowym powoduje:

for_jennifer =

     8     2     5     1


for_kate =

     4     7     2     3

który jest równy 16.

Jeśli zagram w mój kod, co jest mniej zabawne, otrzymam bardzo niezoptymalizowane 132 znaki. Pobij to ;)

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

Ostrzeżenie: bardzo brudny kod
Próbuje każdej możliwej permutacji tablicy wejściowej.

Próbka ideone dla 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!');

Pyton:

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]

lub nieco golfizowany:

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]

Lub jeszcze bardziej golfizowany, ponieważ połowa linii to tylko makijaż. (zakładając, że mogę po prostu zrzucić surową tablicę wewnętrzną, ponieważ nie jest to określone w op) Możesz zostawić print(na przykład) interaktywną powłokę i dodać [::-1](na samym końcu po [0]), jeśli naprawdę chcesz ostatnia różnica.

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]

(wyniki w (0, ((1, 2, 7, 8), (3, 4, 5, 6))))

Jest to jednak brutalne wymuszanie wszystkich możliwych kombinacji i nie powinno być uważane za zdalnie skuteczne. Jeśli jednak lista o równej długości nie ma znaczenia, działałoby to również (na dużych tablicach):

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

Na przykład pod tym kodem działa on z niewielką różnicą: 500k przy wartości maks. 10 ^ 10 to niewiele, że tak powiem. Jest to również o wiele szybsze: tam, gdzie drugi kod prawdopodobnie nie skończyłby się przed upływem roku (i to jest bardzo optymistyczne), działa to w około pół sekundy, nawet jeśli twój przebieg może się różnić.

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

Pisz Haskell

> import Data.List
> import Data.Function

Wykorzystałem monadę listy, aby ją podzielić.

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

Potem robimy oceniającego.

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

A potem funkcja, która zminimalizuje różnicę.

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

I coś, co łączy je wszystkie.

> bestDivison=best . divide

Następnie parser.

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

I formatator wyjściowy.

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

A teraz program

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

Przykład:

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

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