Einfaches Informatikproblem

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.

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.

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

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.

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.

#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]);
      }
    }
}

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

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

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 ;)

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

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

Gibt es das auch in Deutsch

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

1

final int N = 1000; //maximale summe

2

int summands[] = {600,500,300,40,21,1}; //verfügbare summanden

3

int min[] = new int[N+1]; //minimale Anzahl an Summanden für Summe [0,N]

4

Arrays.fill(min, 0);

5

6

for (int i = 0; i <= N; i++)

7

{

8

  for (int j = 0; j < summands.length; j++)

9

  {

10

    if (summands[j] <= i && min[i-summands[j]]+1 < min[i])

11

    {

12

      min[i] = min[i-summands[j]] + 1;

13

    }

14

  }

15

}

16

17

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

Achja es sollte natürlich

1

Arrays.fill(min, Integer.MAX_VALUE);

2

min[0] = 0;

heißen