Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » aud » Forendiskussionen » codezuraufgabe7
import java.util.*; public class Jul16_Backtrack { public static void main(String[] args) { List<Long> in =new LinkedList<Long>(Arrays.asList(23L, 45L, -34L, 12L, 0L, 98L, -99L, 4L, 189L, -1L, 4L)); List<Long> y = new LinkedList<Long>(Arrays.asList(45L, -34L, 12L, 98L, -1L)); List<Long> z = new LinkedList<Long>(Arrays.asList(23L, 0L, -99L, 4L, 189L, 4L)); Tauziehen test=new Tauziehen(); System.out.println(test.tauziehen(in).toString()); } } class Tauziehen { private static List<Long> a, b, y, z; private static long abDiff, yzDiff; public static List<List<Long>> tauziehen(List<Long> in) { a = new LinkedList<>(in); // erste Arbeitsliste (Kopie von in) b = new LinkedList<>(); // zweite Arbeitsliste (anfangs leer) y = null; // erste Ergebnisliste z = null; // zweite Ergebnisliste abDiff = 0; // Differenz der Summe der Werte in a bzw. b yzDiff = 0; // Differenz der Summe der Werte in y bzw. z for (Long v : a) { abDiff += v; } helfer(0); System.out.println("abDiff= " +abDiff + " | yzDiff= " +yzDiff); return Arrays.asList(y, z); } private static void helfer(int p) { // p durchlaeuft alle Positionen in a // Basisfall a und b (fast) gleich gross erreicht? if (Math.abs(a.size() - b.size()) <= 1) { if (y == null && z == null // erste Loesung benoetigt // oder bessere Loesung gefunden || (Math.abs(abDiff) < Math.abs(yzDiff))) { // merke beste bisher gefundene Loesung: y = new LinkedList<>(a); System.out.println(y.toString() +" : Sum="+getSum(y)); z = new LinkedList<>(b);System.out.println(z.toString()+" : Sum="+getSum(z)); System.out.println("abDiff= " +abDiff + " | yzDiff= " +yzDiff);System.out.println() ; yzDiff = abDiff; } } else if (p < a.size()) { // kein Abbruch // Rekursion 1: p-ter Wert bleibt in a: helfer(p + 1); // Rekursion 2: p-ten Wert von a nach b verschieben: abDiff-=2*(a.get(p)); b.add(a.remove(p)); helfer(p); // Backtracking zur 2. Rekursion: abDiff+=2*b.get(b.size()- 1); a.add(p, b.remove(b.size() - 1)); } } private static String getSum(List<Long> y2) { int res=0; for(Long e:y2) res +=e; return res+""; } }