Set in 2 gleichgroße Teile zerlegen

[techdevil]

Hi,

In einem Array liegen beliebig viele natürliche zahlen. Nun möchte ich einen Algorithmus, der das Array in 2 Teile mit gleicher Summe partitioniert oder, wenn das nicht möglich ist, eben das ausgibt.
Beispiel: A={1,2,997,1000}
Ausgabe: "Summe: 1000"
Jemand eine Idee?

 

[function]

erst einmal würde ich alle zahlen des arrays addieren und mit %2 gucken ob es überhaupt 2 gleich große teile geben kann... Wenn das klappt die größte zahl nehmen und versuchen zahlen zuaddieren um "die hälfte" zusammen zu addieren...
das array vorab sortieren hilft oftmals...

 

[techdevil]

Ok, habe das Array sortiert.
Aber wie mache ich das mit der Addition und der Überprüfung, ob es die Hälfte ist...

 

[function]

int sum = 0;
for(int ele : zahlenArray)
 sum += ele;

if( sum%2 == 1) 
  // geht nicht...

sowas zb. wie man das programm weiter baut kannst du ja selbst überlegen und was posten

 

[techdevil]

Mein Problem ist eigentlich, dass bei der Addition auch ein Element ausgelassen werden kann.
Hier wäre die Summe z.B. 21:
Array={1,4,4,5,6,10,12};
Das Erreicht man Aber nur mit 12,5,4 bzw. 10,6,4,1
Ich weiss nicht, wie ich da welche for-schleifen schachteln soll...

 

[function]

was ich gepostet habe sollte war auch nur quasi ein vorab test, weil wenn die gesamt summe des arrays nicht durch 2 teilbar ist, dann kann man das array auch nciht in 2 gleich "große" arrays teilen...

 

[techdevil]

Ja so einen Test hab ich auch schon eingebaut.
Aber das Herzstück fehlt leider noch...

 

[Marco13]

Nur so als Einwurf: Das ist wohl das Partition problem - Wikipedia, the free encyclopedia !?

 

[function]

für den groben alg.: bei deinem beispiel kommst du in etwa auf so einen ablauf:
12+1 < 21 -> 12+1+4 < 21 -> 12+1+4+4 == 21 fertig

noch ein anderes beispiel:
{1, 2, 4, 4, 5, 6}
6+1 < 11 -> 6+1+2 < 11 -> 6+1+2+4 > 11 -> abbruch
6+1+4 = 11 fertig

 

[techdevil]

double sum=Array[Array.length-1];
			for(int i=0;i<Array.length;i++){
				
				sum=sum+Array[i];
				if(sum>b){?}
				if(sum==b){break;}
				if(sum<b){void}
			}

b ist hier also "die Hälfte".
Komme aber nicht weiter...

 

[Marco13]

Das schöne bei NP-vollständigen Problemem: Man braucht gar nicht erst zu versuchen, sich eine effiziente Lösung zu überlegen

In diesem Fall kann man die Lösung folgendermaßen finden: Man betrachtet alle möglichen Teilmultimengen der Eingabemultimenge. Für jede dieser Teilmultimenge bestimmt man die Differenz zwischen der Eingabemultimenge und der Teilmultimenge (also den Rest, der nicht in der Teilmultimenge ist...). Wenn die Teilmultimenge und die Differenz die gleiche Summe ergeben, ist man fertig.

Eigentlich musst du nur alle Teilmultimengen der Eingabemultimenge bestimmen können... wenn man das erstmal hat (hier mal mit dem "PowerSetIterable" von http://www.java-forum.org/codeschnipsel-u-projekte/81973-combinatorics.html gelöst) ist der Rest ganz einfach:

public class Partitioning
{
    public static void main(String args[])
    {
        partition(new int[]{1,2,997,1000});
        partition(new int[]{1,4,4,5,6,10,12});
        partition(new int[]{1,4,4,5,6,11,10,12});
    }
    
    private static void partition(int array[])
    {
        Integer input[] = new Integer[array.length];
        for (int i=0; i<array.length; i++)
        {
            input[i] = array[i];
        }
        PowerSetIterable<Integer> psi = new PowerSetIterable<Integer>(input);
        for (Integer a[] : psi)
        {
            List<Integer> x = Arrays.asList(a);
            List<Integer> y = difference(Arrays.asList(input), x);
            if (sum(x) == sum(y))
            {
                System.out.println(
                    "Result for "+Arrays.toString(input)+
                    " with sum "+sum(x));
                System.out.println(x);
                System.out.println(y);
                return;
            }
        }
        System.out.println("No result for "+Arrays.toString(input));
    }
    
    private static List<Integer> difference(List<Integer> a, List<Integer> b)
    {
        List<Integer> result = new ArrayList<Integer>(a);
        for (Integer i : b)
        {
            result.remove(i);
        }
        return result;
    }
    
    private static int sum(Collection<Integer> c)
    {
        int sum = 0;
        for (Integer i : c)
        {
            sum += i;
        }
        return sum;
    }
}

Ausgabe:

Result for [1, 2, 997, 1000] with sum 1000
[1, 2, 997]
[1000]
Result for [1, 4, 4, 5, 6, 10, 12] with sum 21
[1, 4, 6, 10]
[4, 5, 12]
No result for [1, 4, 4, 5, 6, 11, 10, 12]

 

[techdevil]

ohje...danke..

 

[Marco13]

Ne, is nicht so schlimm

Du hast einen Array, und brauchst alle möglichen Teil-Arrays - das ist das eigentlich schwierige... (Ist das eine Hausaufgabe?)

 

[techdevil]

Ja ist es.

 

[Marco13]

Hmja, da man sich vermutlich auf Eingaben mit weniger als 32 (oder meinetwegen 64) Elementen beschränken kann, kann man das mit dem Bitmuster einer Zahl erledigen, die man hochzählt. Sag' bescheid wenn's da Schwierigkeiten gibt.