Für all diejenigen die zu viel Zeit haben.

[tuxedo]

Wie der Titel schon sagt: Wer zu viel Zeit hat kann sich ja mal an folgende Aufgabe machen... Ich selbst krieg sie nicht so ohne weiteres gebacken. Vielleicht hat ja jmd. von euch ne grandiose Idee und kann mir einen strukturellen Java-Ansatz verraten. Stehe wie der Ochs vorm Berge und find den Weg nicht:

Schreiben Sie ein Programm, das für einen Vektor a = (a1, . . . , an) mit ai Element aus N (natürliche Zahlen) und eine Zahl b Element aus N (natürliche Zahlen) einen Vector x = (x1, . . . , xn) mit xi Element aus {0, 1} findet mit {[mathematisches Summenzeichen], von i=1 bis n}ai * xi = b.
Verwenden Sie dynamische Programmierung. Testen Sie Ihr Programm, auch mit a =
(1, 13, 68, 211, 484, 905, 1588, 2487, 3770, 5409, 7270, 9923, 13116, 16701, 21404,
25903, 31942, 38573, 46302, 54819) sowie b = 100000, b = 200000 und b = 250000.

Die Aufgabe stammt im übrigen aus der Vorlesung "Algorithmen und Datenstrukturen" aus dem 4. Semester im Studium Software-Engineering (FH)

Viel Spaß.

Alex

 

[Bleiglanz]

soviel Zeit braucht man dazu auch nicht

in mathematischer schreibweise will man wohl die gleichung

A x = b

lösen mit einer n x 1 matrix A, einem n-Tupel b. Gesucht ist ein n-Tupel x. Lies einfach mal nach unter "lineare Gleichungssysteme"

(der homogene Fall Ax=0 soll wohl unter den Tisch fallen, der Lösungsraum hat in diesem Fall die Dimension d-1

also

wenn b=0, dann nehmen wir x=0

wenn A=0 und b!=0, dann gehts nicht

wenn A=0 und b=0 dann tuts jedes beliebige x

wenn b!=0 und A!=0 dann meditieren wir ein bisschen über

a1*x1+....+a_n*x_n = b

angenommen a1!=0, dann ist

x_1 = b/a1, x_2=0, ... ,x_n=0

eine Lösung, und weils ja wegen A!=0 ein a_j gibt mit a_j!= 0 ist schon alles erledigt

Das jetzt in eine Java Programm zu packen ist reine Tipparbeit

 

[Guest]

@Bleiglanz: Deine Lösung wäre viel zu leicht und ist falsch.
Bei deiner Lösung müsste das xi eine reelle Zahl sein. xi darf aber nur 0 oder 1 sein.

Die Aufgabenstellung mal anders:

Suche aus einer Liste A die Zahlen heraus, die zusammengezählt b ergeben. Keine Zahl darf doppelt verwendet werden.
Vielleicht ist es jetzt verständlicher.

Anmerkung: Ich bin auch Student dieser FH und auch in diesem Studiengang, aber ein Semester drunter.

Über eine Lösung muss ich erst noch Nachdenken, einen Ansatz hab ich aber wahrscheinlich.

 

[Bleiglanz]

Oooops sorry, nicht genau gelesen, hab gedacht wir sind über den rellen Zahlen

so gesehen schauts nach einem sog. Rucksackproblem oder direkt nach einem NP-vollständigen Problem aus (reine Mutmassung jetzt mal von mir), gibts da wirklich einen Algorithmus dafür oder soll man das mit cleverem Probieren machen?

Müsste ich auch mal drüber nachdenken, aber ausser durchprobieren fällt mir erst mal nichts ein. Mit Sicherheit ist das ganze nicht für jede Zahl b lösbar

Würde mal naiv so eine Art clevere Beschneidung mit Rekursion vorschlagen (einfach mal laut vor mich hingedacht)

wenn irgenein a_j = b sind wir fertig

dann mal alle a_j > b wegwerfen

nimm für jedes a_j <b die analogen Probleme j=1..n

Menge ist {a_1,...a_n} \ {a_j} und Ziel = b-a_j

und jetzt rekursiv weiter...

wenn dabei alle Zahlen der linken Seite > rechte Seite, dann braucht man den Zweig nicht mehr weiter zu verfolgen (das spart hoffentlich ein bissl was und man muss nicht alle 2^n Fälle durchmachen

möglicherweise gibts noch ein paar andere "Beschneidungstricks"

 

[tuxedo]

Lösung gefunden. Das Stichwort war "Rucksackproblem"...
Hätte das Teil auch selbst programmiert, aber der Zeitdruck verlangt es im Netz zu googeln...(muss ja auch noch meinen Lispinterpreter und mein (verteiltes) Auktionshaus programmieren).

Die Lösung gibts hier:

/*************************************************************************
 *  Compilation:  javac Knapsack.java
 *  Execution:    java Knapsack N P W
 *
 *  Generates an instance of the knapsack problem with N items,
 *  profits between 0 and P-1, weights between 0 and W-1,
 *  and solves it in O(NW) using dynamic programming.
 *
 *  %  java Knapsack 6 1000 2000
 *  item    profit  weight  take
 *  1       697     1248    false
 *  2       547     224     false
 *  3       815     776     false
 *  4       342     495     true
 *  5       893     1483    true
 *  6       865     1251    false
 *
 *************************************************************************/

public class Knapsack {

    public static void main(String args[]) {
        int N = Integer.parseInt(args[0]);
        int P = Integer.parseInt(args[1]);  // maximum profit
        int W = Integer.parseInt(args[2]);  // maximum weight
        int[] profit = new int[N+1];
        int[] weight = new int[N+1];

        // generate random instance, items 1..N
        for (int n = 1; n <= N; n++) {
            profit[n] = (int) (Math.random() * P);
            weight[n] = (int) (Math.random() * W);
        }

        // opt[n][w] = max profit of packing items 1..n with weight limit w
        // sol[n][w] = true if opt solution to pack items 1..n with weight limit w
        //             includes item n
        int[][] opt = new int[N+1][W+1];
        boolean[][] sol = new boolean[N+1][W+1];
        for (int n = 1; n <= N; n++) {
            for (int w = 1; w <= W; w++) {
                int option1 = opt[n-1][w];        // don't take item n
                int option2 = Integer.MIN_VALUE;  // take item n
                if (weight[n] < w) option2 = weight[n] + opt[n-1][w-weight[n]];
                opt[n][w] = Math.max(option1, option2);
                sol[n][w] = (option2 > option1);
            }
        }

        // determine which items to take
        boolean[] take = new boolean[N+1];
        for (int n = N, w = W; n > 0; n--) {
            if (sol[n][w]) { take[n] = true;  w = w - weight[n]; }
            else           { take[n] = false;                    }
        }

        // print results
        System.out.println("item" + "\t" + "profit" + "\t" + "weight" + "\t" + "take");
        for (int n = 1; n <= N; n++)
            System.out.println(n + "\t" + profit[n] + "\t" + weight[n] + "\t" + take[n]);
        System.out.println();


    }
}

Quelle: http://www.cs.princeton.edu/introcs/96optimization/Knapsack.java.html vom 19.11.2004 16:45

Gruß und Danke für den "Rucksacktip",
Alex