AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren

Dynamische Programmierung Partition Problem

Ein Thema von Xzeer · begonnen am 8. Jun 2012 · letzter Beitrag vom 8. Jun 2012
Antwort Antwort
Benutzerbild von Xzeer
Xzeer

Registriert seit: 6. Jul 2007
106 Beiträge
 
#1

Dynamische Programmierung Partition Problem

  Alt 8. Jun 2012, 09:33
Hallo zusammen,

es geht um folgendes Problem: Partition problem

Eingabe: Eine Liste mit Integerwerten
Gesucht: Der Wahrheitswert, ob die Liste in zwei Unterlisten mit gleicher Summe zerlegt werden kann

Im oben verlinkten Wikipediaartikel ist ja ein dynamischer Algorithmus angegeben. Doch entweder habe ich den nicht richtig verstanden oder der ist irgendwie falsch. Wenn ich den so übernehme, bekomme ich immer eine ArrayOutOfBounds-Exception in Zeile 8. Ist ja eigentlich auch logisch, weil im ersten Schleifendurchlauf ist i = 1 und j = 1. Wenn jetzt in der Liste an Indexposition 1 ein Wert größer als 1 steht, wird der Wert i-S[j] doch zwangsweise negativ und liegt dann außerhalb von P.

Habe ich da jetzt einen Denkfehler oder ist der wirklich nicht ganz korrekt?
Marvin
Xzeer
  Mit Zitat antworten Zitat
Benutzerbild von spaxxn
spaxxn

Registriert seit: 19. Nov 2004
253 Beiträge
 
Delphi XE2 Enterprise
 
#2

AW: Dynamische Programmierung Partition Problem

  Alt 8. Jun 2012, 11:28
Mit deinem bisher erstellten Quelltext, könnte man dir mit Sicherheit weiterhelfen...
"Hey Süße,
hol mir mal was zu trinken! Du wirst schon wieder hässlich!"

Zitat eines Betrunkenen
  Mit Zitat antworten Zitat
Iwo Asnet

Registriert seit: 11. Jun 2011
313 Beiträge
 
#3

AW: Dynamische Programmierung Partition Problem

  Alt 8. Jun 2012, 11:58
Zitat von Wikipedia:
INPUT: A list of integers S
OUTPUT: True if S can be partitioned into two subsets that have equal sum
Code:
1 function find_partition( S ):
2     N = sum(S)
3     P = empty boolean table of size (N/2 +  1) by (n + 1)
4     initialize top row (P(0,x)) of P to True
5     initialize leftmost column (P(x, 0)) of P, except for P(0, 0) to False
6     for i from 1 to N/2
7          for j from 1 to n
8          P(i, j) ← P(i, j-1) or P(i-S[j], j-1)
9     return P(N/2 , n)
Sehe ich auch so, das für jedes S[j]>i ein Problem auftritt.
Die For-J-Schleife über alle Elemente von S geht zudem bis zur Summe aller Elemente von S und dann knallt es auch. Beispiel:
Code:
S = (1,2,3) (also Elemente 0,1,2.
N = 1+2+3 = 6
For j:=1 to 6 S[j] <--- puff

Geändert von Iwo Asnet ( 8. Jun 2012 um 12:34 Uhr)
  Mit Zitat antworten Zitat
Benutzerbild von DeddyH
DeddyH

Registriert seit: 17. Sep 2006
Ort: Barchfeld
27.463 Beiträge
 
Delphi 11 Alexandria
 
#4

AW: Dynamische Programmierung Partition Problem

  Alt 8. Jun 2012, 11:59
Arrayindizes fangen bei Low(Array) an, was bei dynamischen immer 0 ist, bei statischen aber frei definiert werden kann.
Detlef
"Ich habe Angst vor dem Tag, an dem die Technologie unsere menschlichen Interaktionen übertrumpft. Die Welt wird eine Generation von Idioten bekommen." (Albert Einstein)
Dieser Tag ist längst gekommen
  Mit Zitat antworten Zitat
Benutzerbild von spaxxn
spaxxn

Registriert seit: 19. Nov 2004
253 Beiträge
 
Delphi XE2 Enterprise
 
#5

AW: Dynamische Programmierung Partition Problem

  Alt 8. Jun 2012, 12:09
Bei mir steht gerade eher die Frage im Raum, ob die Länge des Arrays gesetzt wurde
"Hey Süße,
hol mir mal was zu trinken! Du wirst schon wieder hässlich!"

Zitat eines Betrunkenen
  Mit Zitat antworten Zitat
Benutzerbild von DeddyH
DeddyH

Registriert seit: 17. Sep 2006
Ort: Barchfeld
27.463 Beiträge
 
Delphi 11 Alexandria
 
#6

AW: Dynamische Programmierung Partition Problem

  Alt 8. Jun 2012, 13:36
Mit Code wäre das leichter zu klären
Detlef
"Ich habe Angst vor dem Tag, an dem die Technologie unsere menschlichen Interaktionen übertrumpft. Die Welt wird eine Generation von Idioten bekommen." (Albert Einstein)
Dieser Tag ist längst gekommen
  Mit Zitat antworten Zitat
Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 09:36 Uhr.
Powered by vBulletin® Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2021 by Daniel R. Wolf