Einfaches Informatikproblem

[Bert W. (Firma: Wellmann) (dein_v)]

Wie geht man in der Informatik an folgendes Problem einfach heran:

Es ist eine Zahl gegeben, etwa 800.

Dieser will man sich nun mit möglichst wenigen vorgegebenen Zahlen durch 
Addition annähern.

Vorgegeben sind etwa 470, 330, 10, 1.

Im Beispiel also:
470 + 330 = 800 -> Zwei vorgegebene Zahlen verwendet, gut.
10 + 10 + 10 + 470 ... -> mehr als 2
330 + 10 + 10 .... -> mehr als 2
1 + 1 + 1 + 1 ... -> viel mehr als 2

Ich will also eine Liste einlesen mit vorgegebenen Zahlen.

Dann gebe ich ein 800.

Das Programm gibt mir aus -> Am besten erreichbar durch 470 + 330.

[Peter II (Gast)]

wenn es wirklich nur ein paar zahlen sind - dann brute force( einfach 
alle Kombinationen ausprobieren). Wenn es genau passt kann man ja 
abbrechen. Optimieren kann man dadurch das man erst die größte noch 
freihe Zahl verwendet.

Das ganze ist nicht weiter kompliziert, man braucht eventuell mehr code 
für das einlesen und ausgeben als für die Berechnung.

[scheiß "gast"-sperre (Gast)]

Ich habs eilig.

1. Geht um Widerstände oder?
2. Falls es Hausaufgaben sind: Machen wir nicht.
3. wenn 1==true guck mal in der Artikelsammlung, irgendwo sind da 
Programme verlinkt die genau sowas machen.
4. wenn 1==true && 2==false && 3 nichts bringt posten, der Algo ist auf 
den ersten Blick nicht schwierig.

[micha (Gast)]

Brute-force: Berechne alle Kombinationen, sortiere nach Anzahl Summanden 
und gib das/die Minima aus.

Da Du aber das Minimum an Summanden suchst geht es auch geschickter 
(Annahme die Summanden sind sortiert)

erster Summand == Ergebnis?
Ja, super, fertig (eventuell andere Summanden ausprobieren)
< Ergebnis : nächster Summand, s.o.
> Ergebnis : zurück zum Anfang, neuer erster Summand

[Bert W. (Firma: Wellmann) (dein_v)]

Das Problem ist gelöst.

Um meinen Mitteilungsdrang zu befriedigen und wens interessiert: Es ging 
um Widerstände. Ein "simples" Spannungsteilerprogramm.

Beispiel:
Eingangsspannung 5,04V
Gewollte Spannung 1,4V

Ausgabe sortiert nach Abweichung:
Abweichung(Soll Ist) - R_Außen = Widerstand1 + Widerstand2 + Rest für 
R_Innen = Widerstand über dem die Spannung abgegriffen wird.

0.001657(S1.4 I1.401657) - R_Außen = 1000 + 220 + 2.000000 für R_Innen = 
470
0.001657(S1.4 I1.401657) - R_Außen = 10000 + 2200 + 20.000000 für 
R_Innen = 4700
0.001657(S1.4 I1.401657) - R_Außen = 100000 + 22000 + 200.000000 für 
R_Innen = 47000
0.001657(S1.4 I1.401657) - R_Außen = 1000000 + 220000 + 2000.000000 für 
R_Innen = 470000
0.003544(S1.4 I1.403544) - R_Außen = 470 + 100 + 2.000000 für R_Innen = 
220
0.003544(S1.4 I1.403544) - R_Außen = 4700 + 1000 + 20.000000 für R_Innen 
= 2200
0.003544(S1.4 I1.403544) - R_Außen = 47000 + 10000 + 200.000000 für 
R_Innen = 22000
0.003544(S1.4 I1.403544) - R_Außen = 470000 + 100000 + 2000.000000 für 
R_Innen = 220000
0.027762(S1.4 I1.427762) - R_Außen = 2200 + 330 + 70.000000 für R_Innen 
= 1000
0.027762(S1.4 I1.427762) - R_Außen = 220000 + 33000 + 7000.000000 für 
R_Innen = 100000
0.034535(S1.4 I1.434535) - R_Außen = 330 + 47 + 13.000000 für R_Innen = 
150
0.053846(S1.4 I1.453846) - R_Außen = 2200 + 1500 + 200.000000 für 
R_Innen = 1500
0.071858(S1.4 I1.471858) - R_Außen = 470 + 330 + 58.000000 für R_Innen = 
330
0.071858(S1.4 I1.471858) - R_Außen = 47000 + 33000 + 5800.000000 für 
R_Innen = 33000
0.073684(S1.4 I1.473684) - R_Außen = 22000 + 2200 + 1800.000000 für 
R_Innen = 10000
0.108790(S1.4 I1.508790) - R_Außen = 100 + 10 + 12.200000 für R_Innen = 
47
0.127273(S1.4 I1.527273) - R_Außen = 220 + 10 + 30.000000 für R_Innen = 
100
0.280000(S1.4 I1.680000) - R_Außen = 1 + 1 + 0.600000 für R_Innen = 1
0.280000(S1.4 I1.680000) - R_Außen = 10 + 10 + 6.000000 für R_Innen = 10
2.100000(S1.4 I3.500000) - R_Außen = 220000 + 220000 + 2160000.000000 
für R_Innen = 1000000
2.731148(S1.4 I4.131148) - R_Außen = 220000 + 220000 + 4760000.000000 
für R_Innen = 2000000

[Dom (Gast)]

1. Sortier die Summanden nach ihrer Größe (absteigend)

2. Versuche den größten Summanden von der gesuchten Zahl abzuziehen.

Wenn kleiner Null -> nächsten Summand abziehen und Zahl natürlich so 
lassen.

Wenn größer Null und größer als der momentane Summand -> Summand 
auflisten und den Summand nochmal abziehen.

Wenn größer Null aber kleiner als der momentane Summand -> Summand 
auflisten und den nächsten ausprobieren.


Das fällt mir jetzt ganz spontan als erstes ein.

[Bert W. (Firma: Wellmann) (dein_v)]

Soll = Spannungsteiler mit R_Außen = Widerstand1 + Widerstand2 + Rest
Ist = Spannungsteiler mit R_Außen = Widerstand1 + Widerstand2

[U.R. Schmitt (Gast)]

Dom schrieb:
> 1. Sortier die Summanden nach ihrer Größe (absteigend)
>
> 2. Versuche den größten Summanden von der gesuchten Zahl abzuziehen.
>
> Wenn kleiner Null -> nächsten Summand abziehen und Zahl natürlich so
> lassen.
>
> Wenn größer Null und größer als der momentane Summand -> Summand
> auflisten und den Summand nochmal abziehen.
>
> Wenn größer Null aber kleiner als der momentane Summand -> Summand
> auflisten und den nächsten ausprobieren.
>
>
> Das fällt mir jetzt ganz spontan als erstes ein.

Das ist mir auch als erstes eingefallen, die möglichen Werte sortieren 
und vom Größten her den Rest auffüllen
Aber wenn du z.B. 1000 treffen willst und hast 600 500 300 200 100 dann 
kommst du auf 600 + 300 + 100 = 1000, aber nicht auf 500 + 500 = 1000.

Insofern doch nicht ganz trivial.


Dein V. schrieb im Beitrag #2198964:
> Du sollst daraus schließen, daß es respektlos ist zu
> unterstellen es seien Hausaufgaben. Jedem gegenüber. Demjenigen
> gegenüber, bei dem es Hausaufgaben sind

Und du solltest erst mal Respekt denen gegenüber lernen, die dir helfen 
sollen.

[MM (Gast)]

#define MAXLIST 5

int Liste[MAXLIST] = {40, 30, 20, 10, 1}; // sortiert keine 0
int Ergebnis[MAXLIST];


// quick and dirty

void MinAdd(void)
  {
  int Quelle = 123;

  int Ziel = 0, i,j;

  for(i = 0; i < MAXLIST; i++)
    {
    do
      {
      if( (Liste[i] + Ziel) <= Quelle)
        {
        Ziel += Liste[i];
        Ergebnis[i]++;
        }
      else
        {
        break;
        }
      }while(1);
    }
  // Ausgabe
  for(i = 0; i < MAXLIST; i++)
    {
    for(j = 0; j < Ergebnis[i]; j++)
      {
      printf("%d ", Liste[i]);
      }
    }
}

[Peter II (Gast)]

MM schrieb:
> // quick and dirty

und nicht optimal, denn es kommt damit nicht auf lösungen wo ebend nicht 
die größten werden verwendet werden.

siehe:
Autor: U.R. Schmitt (Gast)
Datum: 26.05.2011 09:58

[Uwe (Gast)]

http://www.tilman.de/uni/ws03/alp/greedy.php

[Vlad T. (vlad_tepesch)]

vom Prinzip ist das eine Art Rucksack-Problem

[Yalu X. (yalu) (Moderator)]

Ok, wenn hier gerade mit Fachbegriffen umhergeschmissen wird:

  Dynamische Programmierung

Damit lässt sich Problem sehr rechenzeit- aber nicht ganz so speicher-
effizient lösen.

[D. I. (Gast)]

Yalu X. schrieb:
> Ok, wenn hier gerade mit Fachbegriffen umhergeschmissen wird:
>
>   Dynamische Programmierung
>
> Damit lässt sich Problem sehr rechenzeit- aber nicht ganz so speicher-
> effizient lösen.

Mist das Stichwort wollte ich auch gerade in den Raum werfen :(, um 
genau dabei handelt es sich.

Standardproblem mit DP und extrem einfach wenn man immer eine 1 hat

http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=dynProg

Das erste Eingangsproblem ist genau dein Problem, linear in Zeit und 
Speicherbedarf

Und wie weiter oben schon jemand festgestllt hat, nicht alles geht 
Greedy ;)

[Paul Baumann (Gast)]

Grotesque schrob:
>Mist das Stichwort wollte ich auch gerade in den Raum werfen :(

Wenn man Etwas in den Raum werfen will, sollte man sich überzeugen, daß
es kein Bumerang ist.

(alte australische Volksweisheit)

;-)
MfG Paul

[Dein V. (Gast)]

D. I. schrieb:
> http://www.topcoder.com/tc?module=Static&d1=tutori...

Gibt es das auch in Deutsch

[D. I. (Gast)]

Dein V. schrieb:
> D. I. schrieb:
>> http://www.topcoder.com/tc?module=Static&d1=tutori...
>
> Gibt es das auch in Deutsch

Nein:

aber hier mal der Code in Java

final int N = 1000; //maximale summe
int summands[] = {600,500,300,40,21,1}; //verfügbare summanden
int min[] = new int[N+1]; //minimale Anzahl an Summanden für Summe [0,N]
Arrays.fill(min, 0);

for (int i = 0; i <= N; i++)
{
  for (int j = 0; j < summands.length; j++)
  {
    if (summands[j] <= i && min[i-summands[j]]+1 < min[i])
    {
      min[i] = min[i-summands[j]] + 1;
    }
  }
}

System.out.printf("Fuer Summe %d brauche ich mindestens %d Summanden\n",N,summands[N]);

Den Algorithmus kann man nun so erweitern dass man sich anschließend 
rekonstruiert welche Münzen man verwendet hat

[D. I. (Gast)]

Achja es sollte natürlich

Arrays.fill(min, Integer.MAX_VALUE);
min[0] = 0;

heißen