CD Zusammensetzung

Welche Möglichkeiten gibt es um eine Berechnung zu programmieren, welche Programme ich von der Größe her zusammen auf eine CD/DVD brennen kann.
Ich möchte die Größe der Medien optimal ausschöpfen.
Im Ordner Tools habe ich jetzt 100 Anwendungen wo das Programm erst einmal die Gesamtgröße ausrechnet. Na kann man schon sagen wie viele CDs/DVDs ich benötige. Aber wie ist es möglich eine optimale Zusammensetzung zu berechnen ?

Hallo alf468,

das ist ein NP-schwieriges Problem, wenn du wirklich die optimale Lösung willst. Aber eine für praktische Bedürfnisse ausreichende Lösung (unter der Voraussetzung, dass eine einzelne Anwendung relativ klein im Vergleich zur Größe einer CD ist), ist die Anwendungen nach Größe zu sortieren, mit den größen Anwendungen zu beginnen und erst am Ende einer CD die Lücke mit kleinen Anwendungen zu füllen. Bei der nächsten CD wieder bei den größten verbliebenen beginnen.

herbivore

Jeden Fall mit jedem Fall vergleichen und den besten dann nehmen (Permutation)

Ich schließ mich herbivore an. Alles mit Allem zu vergleichen ist viel zu aufwendig und ich denke sooo genau braucht alfa468 das auch nicht.

Für den Interessierten: Das Problem heisst in der Informatik "Knapsack" (zu deutsch Rucksack). Es ist in der gleichen Aufwandsklasse, wie z.B. auch das Handelsreisendenproblem, gehört also zu den praktisch unlösbaren ( = in vertretbarer rechnezeit) Problemen, bzw. nur bei relativ wenigen Elementen.

Unter bestimmten Randbedingungen gibt schnellere Lösungen. Und natürlich gibt es diverse Verfahren für "nicht-100%ige" Lösungen.

In CD-Falle handelt es sich um eine solches "vereinfachtes Problem", weil alle Werte ganzzahlig sind (Bytes). Hier eine Lösung in Java mittels Dynamischer Programmierung (Algorithmus nach Sedgewick):

 
public class Knapsack {

/*************************************************************************
 *  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 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();


    }
}

Bei CD-Problem sind profit und weight identisch, nämlich Zahl der Bytes. Ebenson sind P=W (=Gesamtgröße der CD). Aufwand ist nur O(NW). Ein Problem könnte allerdings die Arithmetik werden. Vielleicht reicht long gerade aus. Mit "int" darf man wohl nicht arbeiten.

Alternativ kann man auf KB runden.