mikrocontroller.net

Forum: PC-Programmierung Algorithmus zur Aufteilung auf Listen gesucht


Autor: Torsten Robitzki (Firma: robitzki.de) (torstenrobitzki)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo,
ich suche einen Algorithmus mit möglichst günstiger Laufzeit. Der 
Algorithmus soll in meta template programming implementiert werden, von 
daher wäre ein möglichst einfacher Algorithmus schön.

Der Algorithmus soll eine bestimmte Menge von Elementen auf ein oder 
zwei Listen aufteilen. Jedes Element hat eine bestimmte Länge, die Summe 
der Längen aller Listen-Elemente darf die feste Maximal-Länge einer 
Liste nicht überschreiten. Wenn nur eine Liste nötig ist, um alle 
Element aufzunehmen, dann sollte der Algorithmus diese Lösung finden und 
bevorzugen (Wahrscheinlich ist es da am einfachsten mal die Summe über 
alle Elemente zu bilden). Sind eh zwei Listen nötig, spielt der Füllgrad 
der Listen keine Rolle.

Beispiel:
Maximale-Listen-Länge: 32
Elemente: 7, 7, 22, 6, 4, 18

Lösung:
Liste1: 7, 7, 18 (Summe = 32)
Liste2: 22, 6, 4 (Summe = 32)

Hat jemand 'ne gute Idee?

mfg und schönen Dank im Voraus
Torsten

Autor: Der Andere (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Torsten R. schrieb:
> Wenn nur eine Liste nötig ist, um alle
> Element aufzunehmen, dann sollte der Algorithmus diese Lösung finden

Torsten R. schrieb:
> Sind eh zwei Listen nötig, spielt der Füllgrad
> der Listen keine Rolle.

Dann füll doch erst die eine und wenn die voll ist die andere.

Autor: Kai S. (zigzeg)
Datum:

Bewertung
2 lesenswert
nicht lesenswert
Das ganze ist unter dem Namen "Bin Packing" oder Behaelterproblem 
bekannt.
(einziger Unterschied: die Anzahl der Behaelter ist konstant, bei Dir 
nicht)

Die optimale Loesung ist wohl nur mit Rechenaufwand zu finden 
("durchprobieren"). Es gibt aber ein paar gute Approximationen, siehe:

https://de.wikipedia.org/wiki/Beh%C3%A4lterproblem

zigzeg

Autor: Yalu X. (yalu) (Moderator)
Datum:

Bewertung
1 lesenswert
nicht lesenswert
Man könnte so vorgehen, dass man aus der Menge von Elementen eine
Teilmenge so ermittelt, dass die Summe ihrer Elemente maximal, aber
höchstens 32 ist. Diese Elemente packt man in die erste Ergebnisliste,
für den Rest wird das Vorgehen wiederholt bis alle Elemente aufgebraucht
sind.

Sind die Elemente ganzzahlig und positiv?

Wenn ja, liefert der folgende Algorithmus eine optimale Teilmenge zur
Befüllung der ersten Ergebnisliste:

#include <stdio.h>
#include <stdlib.h>

#define MAXLEN 32

int main(int argc, char *argv[]) {
  static int lastelement[MAXLEN+1];

  // Ermittlung einer Teilmenge der Elemente, deren Summe möglichst
  // nah bei MAXLEN liegt, diesen Wert aber nicht überschreitet

  lastelement[0] = -1;
  for(int i=1; i<argc; i++) {
    int el = atoi(argv[i]);
    for(int len=MAXLEN; len>=0; len--) {
      if(lastelement[len]) {
        int sum = len + el;
        if(sum<=MAXLEN && lastelement[sum]==0)
          lastelement[sum] = el;
      }
    }
  }

  // Ausgabe der gefundenen Elemente

  int len = MAXLEN;
  while(lastelement[len] == 0)
    len--;
  printf("Genutzte Gesamtlänge: %d von %d\n", len, MAXLEN);
  while(len) {
    int el = lastelement[len];
    printf("%d ", el);
    len -= el;
  }
  printf("\n");

  return 0;
}

Der Algorithmus basiert auf dem Prinzip der dynamischen Programmierung
und wird O(n·m) abgearbeitet, wenn n die Anzahl der Elemente und m die
maximale Summe der Ergebnisliste (hier 32) ist. Bei fest vorgegebener
maximaler Summe hat der Algorithmus also lineare Laufzeit.

Beispiel 1: Die Summe von 32 kann exakt erreicht werden:
$ pack 7 7 22 6 4 18
Genutzte Gesamtlänge: 32 von 32
4 6 22 

Beispiel 2: Die Summe von 32 kann nicht erreicht werden, die maximal
mögliche Summe ist 30:
$ pack 1 6 10 5 18
Genutzte Gesamtlänge: 30 von 32
18 5 6 1 

: Bearbeitet durch Moderator
Autor: Draco (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Und die Aufteilung auf die anderen Container? ;-) Das Bin-Packing 
Problem kommt dem schon ziemlich nah. Und da eine Mischung aus FirstFit 
und HighFirst.

Autor: Yalu X. (yalu) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Draco schrieb:
> Und die Aufteilung auf die anderen Container? ;-)

Das habe ich jetzt nicht ausprogrammiert, das Prinzip ist aber einfach:

Nach dem erste Durchlauf entfernt man die bereits genutzten Elemente aus
der Menge und startet den Algorithmus mit der Restmenge erneut.

Beispiel (mit manueller Entfernung der genutzten Elemente ;-)):
$ pack 3 5 13 10 6 7 15 24 14 9 11
Genutzte Gesamtlänge: 32 von 32
6 10 13 3 

$ pack 5 7 15 24 14 9 11   # die Elemente 6, 10, 13 und 3 aus dem ersten
                           # Durchlauf fallen weg
Genutzte Gesamtlänge: 32 von 32
11 14 7 

$ pack 5 15 24 9
Genutzte Gesamtlänge: 29 von 32
24 5 
$ pack 15 9

Genutzte Gesamtlänge: 24 von 32
9 15 

Damit sind alle Elemente aufgebraucht.

Zwei der Container konnten komplett gefüllt werden, die beiden anderen
nicht ganz. Mehr ist aber auch mit einer anderen Auswahl der Elemente
nicht möglich.

Autor: c-hater (Gast)
Datum:

Bewertung
-2 lesenswert
nicht lesenswert
Torsten R. schrieb:

> Der Algorithmus soll eine bestimmte Menge von Elementen auf ein oder
> zwei Listen aufteilen. Jedes Element hat eine bestimmte Länge, die Summe
> der Längen aller Listen-Elemente darf die feste Maximal-Länge einer
> Liste nicht überschreiten. Wenn nur eine Liste nötig ist, um alle
> Element aufzunehmen, dann sollte der Algorithmus diese Lösung finden und
> bevorzugen (Wahrscheinlich ist es da am einfachsten mal die Summe über
> alle Elemente zu bilden). Sind eh zwei Listen nötig, spielt der Füllgrad
> der Listen keine Rolle.

Der Algorithmus ist bei diesen Anforderungen doch ganz einfach:

Elementsumme feststellen
Gucken, ob's in eine Liste passt
Wenn ja, pack's in eine Liste
Wenn nein:
 fülle eine Liste, bis nächstes Element nicht mehr reinpasst
 fülle Rest in zweite Liste

Das ist so trivial, da rollen sich einem bei dem Gedanken, dass für 
dieses Problem irgendwer, der sich für einen Programmierer hält, die 
Lösung erfragen muss, doch gelinde die Zehennägel hoch...

Ich befürchte aber, dass es viel schlimemr ist: Du hast vermutlich nicht 
einmal die Anforderungen korrekt verstanden bzw. hier korrekt 
dargestellt...

Autor: Mark Brandis (markbrandis)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Torsten R. schrieb:
> ich suche einen Algorithmus mit möglichst günstiger Laufzeit. Der
> Algorithmus soll in meta template programming implementiert werden, von
> daher wäre ein möglichst einfacher Algorithmus schön.

Algorithmen haben es so an sich, dass sie von einer konkreten 
Implementierung völlig unabhängig sind.

Autor: Josef (Gast)
Datum:

Bewertung
2 lesenswert
nicht lesenswert
c-hater schrieb:
> Der Algorithmus ist bei diesen Anforderungen doch ganz einfach:
>
> Elementsumme feststellen
> Gucken, ob's in eine Liste passt
> Wenn ja, pack's in eine Liste
> Wenn nein:
>  fülle eine Liste, bis nächstes Element nicht mehr reinpasst
>  fülle Rest in zweite Liste

Mit dem ersten Beispiel 7, 7, 22, 6, 4, 18
ergibt das

Liste 1: 7, 7, 6, 4
Liste 2: 22
Liste 3: 18

Nicht optimal.

Autor: D. I. (Gast)
Datum:

Bewertung
2 lesenswert
nicht lesenswert
c-hater schrieb:
> Das ist so trivial, da rollen sich einem bei dem Gedanken, dass für
> dieses Problem irgendwer, der sich für einen Programmierer hält, die
> Lösung erfragen muss, doch gelinde die Zehennägel hoch...

Tja und wenn man nur ein Programmierer ist versagt man grandios bei 
dieser Aufgabe wie du eindrucksvoll bewiesen hast. Tja es gibt halt nen 
Unterschied zwischen Hobbycodern und ausgebildeten Fachkräften.

Autor: c-hater (Gast)
Datum:

Bewertung
-2 lesenswert
nicht lesenswert
Josef schrieb:

> Mit dem ersten Beispiel 7, 7, 22, 6, 4, 18
> ergibt das
>
> Liste 1: 7, 7, 6, 4
> Liste 2: 22
> Liste 3: 18
>
> Nicht optimal.

Wieso sollte das nicht optimal sein? Jedenfalls im Sinne des von dir 
selber geposten Anforderungswerks. Der Scheiss passt nicht in eine 
Liste, also müssen es zwei sein. Und bei zwei Listen spielt deren 
Füllgrad keine Rolle. Exakt so waren deine Anforderungen, weitere gab es 
in deinem Eröffnungsposting nicht.

Es wird immer deutlicher: Du bist einfach so dermassen krass unfähig, 
dass du nicht einmal die Anforderungen an den gesuchten Algorithmus 
formal korrekt darzustellen vermagst! Kein Wunder, dass du dann auch 
keinen implementieren kannst, der den (tatsächlichen) Anforderungen 
entspricht...

Autor: Mark Brandis (markbrandis)
Datum:

Bewertung
1 lesenswert
nicht lesenswert
Diese zwei Anforderungen widersprechen sich meiner Ansicht nach:

Torsten R. schrieb:
> die Summe der Längen aller Listen-Elemente darf die feste Maximal-Länge
> einer Liste nicht überschreiten.


> Sind eh zwei Listen nötig, spielt der Füllgrad der Listen keine Rolle.

Entweder gibt es allgemein eine maximale Länge für eine Liste (was die 
1. Anforderung auszusagen scheint), oder eben nicht.

Wenn es nur für manche Fälle ein Maximum geben soll, dann muss man 
dies in den Anforderungen klar darstellen.

: Bearbeitet durch User
Autor: Rolf Magnus (rmagnus)
Datum:

Bewertung
2 lesenswert
nicht lesenswert
c-hater schrieb:
> Es wird immer deutlicher: Du bist einfach so dermassen krass unfähig,
> dass du nicht einmal die Anforderungen an den gesuchten Algorithmus
> formal korrekt darzustellen vermagst!

Ganz schön große Töne für jemanden, der leider am lesen der 
Anforderungen gescheitert ist.

c-hater schrieb:
> Wieso sollte das nicht optimal sein? Jedenfalls im Sinne des von dir
> selber geposten Anforderungswerks. Der Scheiss passt nicht in eine
> Liste, also müssen es zwei sein.

Man braucht bei deinem Algorithmus aber nicht zwei, sondern drei Listen 
für die Werte aus dem Beispiel, und das widerspricht dieser Anforderung:

Torsten R. schrieb:
> Der Algorithmus soll eine bestimmte Menge von Elementen auf ein oder
> zwei Listen aufteilen.


Mark B. schrieb:
> Diese zwei Anforderungen widersprechen sich meiner Ansicht nach:
>
> Torsten R. schrieb:
>> die Summe der Längen aller Listen-Elemente darf die feste Maximal-Länge
>> einer Liste nicht überschreiten.
>
>> Sind eh zwei Listen nötig, spielt der Füllgrad der Listen keine Rolle.
>
> Entweder gibt es allgemein eine maximale Länge für eine Liste (was die
> 1. Anforderung auszusagen scheint), oder eben nicht.

Die maximale Länge gibt es doch immer. Füllgrad ist nicht gleich 
maximaler Länge. Der Füllgrad gibt lediglich an, wieviel von der 
maximalen Länge tasächlich genutzt wurde. Es muss also nicht die eine 
Liste ganz voll gemacht werden und die andere möglichst wenig enthalten, 
sondern es kann sich z.B. auch gleichmäßig auf beide Listen verteilen.

> Wenn es nur für manche Fälle ein Maximum geben soll, dann muss man
> dies in den Anforderungen klar darstellen.

Ich kann nicht erkennen, warum das der Fall sein sollte.

Viel eher sehe ich hier einen Widerspruch:

Torsten R. schrieb:
> Hallo,
> ich suche einen Algorithmus mit möglichst günstiger Laufzeit. Der
> Algorithmus soll in meta template programming implementiert werden, von
> daher wäre ein möglichst einfacher Algorithmus schön.

Der einfachste Algorithmus ist meistens nicht gleichzeitig auch der 
schnellste. Man muss also eins von beiden priorisieren.

Autor: Georg (Gast)
Datum:

Bewertung
1 lesenswert
nicht lesenswert
c-hater schrieb:
> fülle eine Liste, bis nächstes Element nicht mehr reinpasst
>  fülle Rest in zweite Liste
>
> Das ist so trivial, da rollen sich einem bei dem Gedanken, dass für
> dieses Problem irgendwer, der sich für einen Programmierer hält, die
> Lösung erfragen muss, doch gelinde die Zehennägel hoch...

Das liegt einfach daran, dass du weder das Problem noch deine angebliche 
Lösung auch nur annähernd verstanden hast. Dass du dich für einen 
Programmierer hältst beleidigt die ganze Zunft, daran ändern auch die 
von dir wie üblich ausgeteilten Beleidigungen nichts. Eine Schande nicht 
nur für das Forum.

Georg

Autor: Torsten Robitzki (Firma: robitzki.de) (torstenrobitzki)
Datum:

Bewertung
1 lesenswert
nicht lesenswert
Hi Kai,

Kai S. schrieb:
> Das ganze ist unter dem Namen "Bin Packing" oder Behaelterproblem
> bekannt.
> (einziger Unterschied: die Anzahl der Behaelter ist konstant, bei Dir
> nicht)

ich hatte schon ein zwei Google-Versuche, aber wenn man nicht weiß wie 
der Rest der Welt das Problem nennt, kommt man natürlich nicht so 
schnell auf die Lösung der Anderen ;-)

Danke schön!

mfg Torsten

Autor: Torsten Robitzki (Firma: robitzki.de) (torstenrobitzki)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hi Yalu,

Yalu X. schrieb:
> Sind die Elemente ganzzahlig und positiv?

Jep!

> Wenn ja, liefert der folgende Algorithmus eine optimale Teilmenge zur
> Befüllung der ersten Ergebnisliste:

Ok, ich versuche das gerade mal zu verstehen... :-)

>   lastelement[0] = -1;
>   for(int i=1; i<argc; i++) {
>     int el = atoi(argv[i]);
>     for(int len=MAXLEN; len>=0; len--) {
>       if(lastelement[len]) {

Hier kann ich Dir nicht mehr folgen: lastelement[len] wäre doch 
lastelement[32] und das wäre meiner Meinung nach undefiniert oder 0. Wo 
ist mein Fehler?

mfg Torsten

Autor: Buber (Gast)
Datum:

Bewertung
1 lesenswert
nicht lesenswert
c-hater schrieb:

> Es wird immer deutlicher: Du bist einfach so dermassen krass unfähig,
> dass du nicht einmal die Anforderungen an den gesuchten Algorithmus
> formal korrekt darzustellen vermagst!

Muss man eine bedauernswerte Kreatur, wie dich, korrekterweise Soziopath 
nennen?  https://de.wikipedia.org/wiki/Soziopathie

Autor: Torsten Robitzki (Firma: robitzki.de) (torstenrobitzki)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Yalu X. schrieb:
> Draco schrieb:
>> Und die Aufteilung auf die anderen Container? ;-)
>
> Das habe ich jetzt nicht ausprogrammiert, das Prinzip ist aber einfach:
>
> Nach dem erste Durchlauf entfernt man die bereits genutzten Elemente aus
> der Menge und startet den Algorithmus mit der Restmenge erneut.

Ja, da es nur 2 Listen gibt, wäre es tatsächlich relativ einfach. Wenn 
man die erste Liste optimal packt, muss der Rest einfach in die zweite 
Liste -> fertig ;-)

Mir sind gerade noch zwei Besonderheiten eingefallen. Für den Fall, dass 
es Vorteilhaft wäre, die Elemente zuerst zu sortieren, dann würde 
eigentlich immer gelten:
- Das größte Element muss in die erste Liste, wenn das nicht passt, gibt 
es auch keine Lösung.
- Wenn das nächst kleinere Element nicht in die erste Liste past, muss 
es in die zweite Liste.
- Erst wenn ein zweites Element in die erste Liste passt, muss bei der 
Suche hier verzweigt werden.

Allerdings müsste man dann vorher sortieren.

Autor: Torsten Robitzki (Firma: robitzki.de) (torstenrobitzki)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Rolf M. schrieb:

> Viel eher sehe ich hier einen Widerspruch:
>
> Torsten R. schrieb:
>> Hallo,
>> ich suche einen Algorithmus mit möglichst günstiger Laufzeit. Der
>> Algorithmus soll in meta template programming implementiert werden, von
>> daher wäre ein möglichst einfacher Algorithmus schön.
>
> Der einfachste Algorithmus ist meistens nicht gleichzeitig auch der
> schnellste. Man muss also eins von beiden priorisieren.

erwischt! ;-)

Autor: Mark Brandis (markbrandis)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Torsten R. schrieb:
> Hier kann ich Dir nicht mehr folgen: lastelement[len] wäre doch
> lastelement[32] und das wäre meiner Meinung nach undefiniert oder 0. Wo
> ist mein Fehler?

Das Array ist so deklariert:

static int lastelement[MAXLEN+1];

Von daher existiert lastelement[32] also.

Autor: Yalu X. (yalu) (Moderator)
Datum:

Bewertung
1 lesenswert
nicht lesenswert
Torsten R. schrieb:
> Ok, ich versuche das gerade mal zu verstehen... :-)

Zum besseren Verständnis noch ein paar Worte zur Bedeutung des Inhalts
von lastelement[]:

  lastelement[len] = el   (el > 0, 0 ≤ len ≤ MAXLEN)

sagt aus, dass bereits eine Teilmenge gefunden wurde, deren Summe gleich
len ist und dass das letzte dieser Elemente el ist. Ist hingegen

  lastelement[len] = 0

wurde noch keine solche Teilmenge gefunden.

Zu Beginn sind alle Elemente von lastelement[] mit 0 intialisiert, nur
lastelement[0] hat den Wert -1, was aussagt, dass bereits eine Teilmenge
gefunden worden ist, deren Summe 0 ist. Diese Teilmenge ist
trivialerweise die leere Menge. Da die leere Menge kein (letztes)
Element hat, wird hier einfach ein beliebiger von 0 verschiedener Wert
(-1) eingetragen.

Im ersten Teil des Algorithmus werden nun für jedes Element der
vorgegebenen Menge die Einträge von lastelement[] aktualisiert, so dass
man daraus am Schluss ablesen kann, welche Summen von 0 bis MAXLEN
überhaupt erreichbar sind.

Im zweiten Teil wird dann zunächst die größtmögliche Summe gesucht
(erste While-Schleife). Danach werden – ausgehend von dieser Summe –
nacheinander die zur entsprechenden Teilmenge gehörenden Elemente
ermittelt (zweite While-Schleife).

Man kann den Algorithmus übrigens noch etwas optimieren, indem man im
ersten Teil eine zusätzliche Abbruchbedingung einbaut, die anspricht,
sobald eine Teilmenge gefunden worden ist, deren Summe exakt MAXLEN ist.
In diesem Fall braucht nicht weitergesucht zu werden, und man kann
direkt zur Ausgabe der Ergebnisse übergehen:

  lastelement[0] = -1;
  for(int i=1; i<argc; i++) {
    int el = atoi(argv[i]);
    for(int len=MAXLEN; len>=0; len--) {
      if(lastelement[len]) {
        int sum = len + el;
        if(sum<=MAXLEN && lastelement[sum]==0) {
          lastelement[sum] = el;
          if(sum == MAXLEN)
            goto perfect_solution_found;
        }
      }
    }
  }

  perfect_solution_found:
  ;

(Militante Goto-Gegner mögen mir die entsprechende Codezeile verzeihen
;-))

Autor: D. I. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hach ja dynamische Programmierung ist schon was feines :) trifft man im 
beruflichen Alltag leider nicht mehr so häufig an.
Ich erinnere mich noch gerne an unser Schokoladengeplänkel Yalu ;)

Autor: Yalu X. (yalu) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
D. I. schrieb:
> Hach ja dynamische Programmierung ist schon was feines :)

Ja, das gibt jedesmal einen kleinen Aha-Effekt, weil man damit oft
Probleme sehr effizient lösen kann, die auf den ersten Blick nur in
exponentieller Zeit lösbar sind.

Trotzdem habe ich nie ganz verstanden, warum das Ganze "Dynamische
Programmierung" heißt.

> Ich erinnere mich noch gerne an unser Schokoladengeplänkel Yalu ;)

Daran erinnerst du dich noch (ist ja schon über drei Jahre her)? Ich
musste gerade nachschauen, worum es da überhaupt ging :)

BTW: Es gibt da seit einiger Zeit einen neuen, schwer zu schlagenden
ersten Platz mit gerade mal 0,000 s (also besser als 1 ms oder sogar
besser als 0,5 ms, je nach Rundungsverfahren):

  https://uva.onlinejudge.org/index.php?option=com_o...

Das warst doch nicht etwa du?

Autor: D. I. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Yalu X. schrieb:
> Trotzdem habe ich nie ganz verstanden, warum das Ganze "Dynamische
> Programmierung" heißt.

Das weiß ich auch nicht wie es zu dieser Begrifflichkeit kam.

Yalu X. schrieb:
> Daran erinnerst du dich noch (ist ja schon über drei Jahre her)? Ich
> musste gerade nachschauen, worum es da überhaupt ging :)

Ja die wenigen interessanten Diskussionen sind noch im Hinterstübchen 
verankert (wie z.B. auch das Backtracking-Bewässerungsproblem). Aber das 
Schokoladenproblem hatte ich erst vor kurzem wo anders verarbeitet, 
daher kam mir das wieder in den Sinn :)

Yalu X. schrieb:
> Das warst doch nicht etwa du?

Nein, ich habe schon längere Zeit nichts mehr eingereicht. Meine Zeit 
ist im Moment eher begrenzt und ich verwende sie im Moment u.a. auf 
Dinge die ein paar € nebenbei versprechen :)

Autor: Clemens L. (c_l)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Yalu X. schrieb:
> Trotzdem habe ich nie ganz verstanden, warum das Ganze "Dynamische
> Programmierung" heißt.

Weil Richard Bellman es so genannt hat: 
https://de.wikipedia.org/wiki/Dynamische_Programmierung

Autor: SearchMe (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Yalu X. schrieb:

> BTW: Es gibt da seit einiger Zeit einen neuen, schwer zu schlagenden
> ersten Platz mit gerade mal 0,000 s (also besser als 1 ms oder sogar
> besser als 0,5 ms, je nach Rundungsverfahren):
>
> 
https://uva.onlinejudge.org/index.php?option=com_o...


Die Quelltexte der Lösungen kann man nicht sehen?

Autor: D. I. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
SearchMe schrieb:
> Die Quelltexte der Lösungen kann man nicht sehen?

Nein, es gibt halt vereinzelt auch retarded Abgaben die einfach nur die 
Lösungen ausgeben. Sowas ist möglich wenn man das input/output set 
findet im Netz. Solche Abgaben werden zwar nach einer Zeit wieder 
entfernt, aber das kann dauern. Aber in diesem Fall scheint die Zahl 
legit zu sein, dieser sgtlaugh scheint sehr ambitioniert zu sein.

Autor: SearchMe (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
D. I. schrieb:
> SearchMe schrieb:
>> Die Quelltexte der Lösungen kann man nicht sehen?
>
> Nein

Schade. Den Unterschied zwischen Platz 2 (86 ms) und Platz 1 (0 ms/1 ms) 
hätte ich gern gesehen.

Autor: D. I. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
SearchMe schrieb:
> Schade. Den Unterschied zwischen Platz 2 (86 ms) und Platz 1 (0 ms/1 ms)
> hätte ich gern gesehen.

Meine Vermutung ist, dass ggü. Yalu er eine bessere Methode hat die 
Teilmengen zu berechnen. (Vermutlich einmalig precomputed) Das wäre mein 
erster Verdacht.

Autor: Torsten Robitzki (Firma: robitzki.de) (torstenrobitzki)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Yalu X. schrieb:
> Zum besseren Verständnis noch ein paar Worte zur Bedeutung des Inhalts
> von lastelement[]:
>
>   lastelement[len] = el   (el > 0, 0 ≤ len ≤ MAXLEN)
>
> sagt aus, dass bereits eine Teilmenge gefunden wurde, deren Summe gleich
> len ist und dass das letzte dieser Elemente el ist. Ist hingegen
>
>   lastelement[len] = 0
>
> wurde noch keine solche Teilmenge gefunden.
>
> Zu Beginn sind alle Elemente von lastelement[] mit 0 intialisiert, nur
> lastelement[0] hat den Wert -1, was aussagt, dass bereits eine Teilmenge
> gefunden worden ist, deren Summe 0 ist. Diese Teilmenge ist
> trivialerweise die leere Menge. Da die leere Menge kein (letztes)
> Element hat, wird hier einfach ein beliebiger von 0 verschiedener Wert
> (-1) eingetragen.

Ok, den Teil hatte ich am Anfang übersehen, ich hatte nur dass innere 
`if` gesehen und mich gefragt: "Wann soll das den ausgeführt werden?" 
;-) Jetzt ist es mir aber klar. Sehr pfiffig! ;-)

Die innere Schleife könnte man noch auf "for(int len=MAXLEN-el; len>=0; 
len--)" verkürzen.

Schönen Dank an Alle! Jetzt muss ich mal gucken, was sich davon am 
besten umsetzen lässt.

mfg Torsten

Autor: Yalu X. (yalu) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Torsten R. schrieb:
> Die innere Schleife könnte man noch auf "for(int len=MAXLEN-el; len>=0;
> len--)" verkürzen.

Stimmt, das würde noch einmal ein paar Schleifendurchläufe einsparen.

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.