100 Gramm aus Euro Münzen

Folgende Aufgabe wurde von dutchman2006 eingereicht:

Eine Goldwaage soll kalibriert werden, dazu wird allerdings ein 100-Gramm-Gewicht benötigt.
Ein solches ist aber nicht verfügbar, daher muss ein 100-Gramm-Gewicht aus anderen Gegenständen "gebastelt" werden: in dieser Aufgabe Euro-Münzen.
Eine Tabelle des exakten Gewichtes aller Euromünzen gibt es hier: *klick*.

Die Aufgabe besteht nun darin, (die genaue Anzahl aller möglichen) Münz-Kombinationen zu finden, die exakt 100 Gramm ausmachen.
Achtet darauf, dass Kombinationen die sich nur in der Reihenfolge der Münzen unterscheiden nicht doppelt gezählt werden.
 
Hi, ich bin leider noch sehr unerfahren in C++, aber ich hoffe, das mein Prog den Anforderungen genügt.
Laut Logik müsste es stimmen. Ich hoffe es schreibt noch jemand eine Lösung in C++, die einen besseren Programmierstil hat. *g*
 
Ich brauch mal ein wenig Hilfe. Mein Programm gibt je nach Datentyp (float oder double) für die Berechnung der Summe ein anderes Ergebnis zurück (float: 2119 Kombinationen; double: 2426 Kombinationen)
Vielleicht weiß ja ein erfahrener C-Coder rat, aber ich habe echt keine Ahnung, was falsch sein könnte. Ich habe stichprobenartig einige Ergebnisse nachgerechnet, habe aber überall das Ergebnis "100" herausbekommen.

Hier mein Code (rekursiver Ansatz):
Code:
#include <iostream>

using namespace std;

void coinComb(short coins[], double sum, int mod);

const double weight[8] = {8.50, 7.50, 7.80, 5.74, 4.10, 3.92, 3.06, 2.30};

int c100 = 0;

int main()
{
    short coins[] = {0, 0, 0, 0, 0, 0, 0, 0};
    coinComb(coins, 0, 0);
    cout << "Genau 100g bei " << c100 << " Kombinationen" << endl;
}

void coinComb(short coins[], double sum, int mod)
{
    while (sum < 100) {
        if (mod != 7 && sum + weight[7] < 100.01) {
            // copy coins
            short coinsCopy[8];
            for (int i = 0; i < 8; ++i) coinsCopy[i] = coins[i];
            coinComb(coinsCopy, sum, mod + 1);
        }
        ++coins[mod];
        sum += weight[mod];
    }
    if (sum < 100.01) {
        c100++;
        for (int i = 0; i < 8; ++i) {
            cout << coins[i] << ' ';
        }
        cout << "sum=" << sum << endl;
    }
}
 
@Eydeet :Bei mir geht dein Prog so fast überhaupt nicht, der zählt einmal sum im 8,5 er Schritt hoch und dann ist Schluss- bei der Ausgabe kommt dann, das es 0 Kombinationen gäbe. K.A. -ich habs einfach mal kopiert und ausgeführt... hm- mahc ich irgendwas verkehrt? Also bei mir springt der Quasi nie in die erste if- Abfrage rein.

PS.: Mein Prog kommt nur auf 276 Möglichkeiten- ich finde das klingt auch realistischer.
 
Ich hab das Ganze noch mal auf Integer umgeschrieben, vielleicht läuft das ja bei dir. Ich bekomme allerdings jetzt 4674 Möglichkeiten ^^. Vielleicht kannst du ja mal deine Ergebnisse posten, und ich guck dann, ob ich Kombinationsmöglichkeiten finde, die du noch nicht hast.

Meine Ausgabe habe ich als Anhang angehängt. Mein Beitrag wäre sonst einfach viel zu lang geworden.

Code:
#include <stdio.h>

void coinComb(short coins[], short sum, short mod);

const int weight[8] = {850, 750, 780, 574, 410, 392, 306, 230};

short c100 = 0;

int main()
{
    short coins[] = {0, 0, 0, 0, 0, 0, 0, 0};
    coinComb(coins, 0, 0);
    printf("~ %i passende Kombinationen gefunden\n", c100);
    return 0;
}

void coinComb(short coins[], short sum, short mod)
{
    while (sum < 10000) {
        if (mod != 7) {
            short coinsCopy[8];
            short i;
            for (i = 0; i < 8; ++i) coinsCopy[i] = coins[i];
            coinComb(coinsCopy, sum, mod + 1);
        }
        ++coins[mod];
        sum += weight[mod];
    }
    if (sum == 10000) {
        short i;
        c100++;
        for (i = 0; i < 8; ++i) {
            printf("%2i ", coins[i]);
        }
        printf("\n");
    }
}

PS: Das mit den C-Gurus habe ich geschrieben, weil es kein C++-Spezifisches Problem war, aber grundsätzlich hast du natürlich Recht. Die neue Version ist übrigens schönes, oder zumindest standardkonformes C ;)
 
ich hab meins jetzt auch noch mal in integer umgeschrieben, und siehe da, ich komme ebenfalls auf 4674 Möglichkeiten! Und ich hatte auch rausgefunden, das der bei double die anderen Möglickeiten auch durchläuft, auch auf 100 kommt, aber komischerweise diese nicht gezählt hat...K.A. woran das liegt. Ich bin dem gestern noch mal auf den Grund gegangen, bin aber bis jetzt zu keinem richtigen Ergebnis gekommen, hab aber noch rausgefunden, dass der total spinnt, wenn ich Ergebnis von long double auf double geändert hab. Irgendwie glaub ich, dass ich ein sehr ähnliches Problem wie du hattest, hatte.
Hier noch mal mein Prog:

Ich hab meine Ergebnisliste ebenfalls angehängt, dürfte jetzt aber irrelevant sein. Dein Prog ist ja auf der gleichen Logik wie meins aufgebaut ist, nur halt eleganter gelöst. Leider bin ich nicht auf den rekursiven Ansatz gekommen...P.S.: Dein erstes Prog ging bei mir gestern schon, so wie von dir beschrieben, ich hab blos vergessen, das die Konsole ja nicht undenlich viele Zeichen aufnimmt :), halt Anfängerfehler...hab dann die Ausgabe umgeleitet, und schwubs waren alle Ergebnisse da.
 
Ich denke mal, dass der Ansatz mit der Einschränkung des Suchraums der einzig tragbare ist. Denn der naive Ansatz:
Code:
//startaufruf mit sum=10000
 public  void getCombination(LinkedList result,int[] coins,int sum)
    {
    	if (sum>0) 
    		for (int coinWeight:coins) getCombination(result,coins,sum-coinWeight);
braucht sehr sehr lange. Meiner groben Einschätzung nach muss man dann nämlich ca 18^8 Möglichkeiten untersuchen (Durchschnittsgewicht einer Münze= 5.36 -> für 100 Gramm braucht man ca 18 Stück).Und das sind 11 Mrd irgendwas.
Code:
import java.util.List;

public class Main
{
        final static int WEIGHT=100*100;    
	final static int coins[]={230,306,392,410,574,780,750,850};  
	
	public static void main(String[] args)
	{
		Combinator comb=new Combinator(coins,WEIGHT);
		List result=comb.getCombinations();
		
		for (Object array:result)
	    	{
			   System.out.println();
			   for (int i:(int[])array)
				   System.out.print(i+" ");
				 
	    	}
	    		
		System.out.println("gesamt: "+result.size());
	}

}


import java.util.LinkedList;
import java.util.List;

public class Combinator
{
   private int[] weight;
   private int limit;
   private int[] comb;
   private LinkedList result=new LinkedList();
   
   private Combinator(){};
   
   public Combinator (int[] combinations,int limit)
   {
	   this.weight=combinations.clone();
	   comb=new int[weight.length];
	   this.limit=limit;	   
   }
   
   private int getSum()
   {
	   int sum=0;
	   for (int i=0;i<comb.length;i++)
		   sum=sum+(weight[i]*comb[i]);
	   return sum;
   }
   
   private boolean next()
	{
	   comb[0]++;	
	   for (int i=0;(i < comb.length-1)&&(getSum()>limit);i++)
		{
			comb[i] = 0;
			comb[i + 1]++;
		}
	  if (getSum() > limit)
		return false;
	  else
		return true;

	}
   
   public List getCombinations()
   {
	   while (next())
		   if (getSum()==limit)
			   result.add(comb.clone());
	   
	   return result;
   }
}
 
Ich hab einen kleinen Counter in beide Programme (deins & meins) eingebaut. (Bei mir: 1. Zeile der coinComb-Funktion, bei dir: 1. Zeile der next-Funktion).
Das Ergebnis:
Code:
CDW   : 3487996 Durchläufe
Eydeet:  600516 Durchläufe
Außerdem habe ich auch irgendwie das Gefühl, dass meine Lösung schneller läuft, rein subjektiv natürlich ;) Mathematisch kann ich das leider nicht belegen, aber an deiner Rechnung scheint irgendwas falsch zu sein.
 
So ists Richtig

Ich hab mir die Aufgabe angeguckt aber eure Lösungsansätze sind bischen komisch weil sie irgendwie etwas Kompliziert gedacht sind auf jedenfall hab ich es auch mal versucht dieses Progrämschen zu Programieren. Bei mir kommen auch 4674 verschiedene Kombinationen raus ich denke das ist richtig hab das stichprobenartig mal nachgerechnet und ich kam immer auf 100.....
 
btw:
eure Lösungsansätze sind bischen komisch weil sie irgendwie etwas Kompliziert gedacht
Eine zig verschachtelte Schleife mit hartkodierten Werten (zur Einschränkung des Suchraums) nutzen und über andere meckern? ne ne ne ;).

Code:
muenze(850).  %ganze zahlen als Gewicht nutzen
muenze(780).
muenze(750).
muenze(574).
muenze(410).
muenze(392).
muenze(306).
muenze(230).

	                             %ist das Gewicht=0, so ist die Kombination trivial (0 Muenzen)
kombination(0,_).
	                             %ansonsten ist das bestenfalls zusammengesetztes Gewicht,
	                             %somit ist die Loesung eine Kombination aus mehreren Muenzen
kombination(Gew,Vor):-  
		                     %es gibt eine Loesung, sofern:
	Gew>0,                       %das Gewicht positiv ist	
        muenze(Teil_gew),            %und es eine Muenze gibt,
	Teil_gew=<Vor,               %die weniger/genausoviel wiegt wie 
	                             %die Vorgaengermuenze,
	Rest is Gew-Teil_gew,        % und diese Muenze und der Rest des Gewichts
	kombination(Rest,Teil_gew).  %zusammen das Wunschgewicht bilden,
	                             %wobei dieser Rest sich natuerlich auch als Muenzkombination
	                             %darstellen laesst
kombinationen(Gew,Erg):-
	Gewicht = Gew*100,
	findall(_,kombination(Gewicht,Gewicht),Anzahl),
	length(Anzahl,Erg).
Die Vorgängermünze wird in der Lösung betrachtet, um Lösungen, die sich nur in der Reihenfolge der Münzen unterscheiden, auszuschließen.

wegen findall/length: es wurde SWI Prolog benutzt - findall bildet eine Liste mit allen Lösungen und length bestimmt die Länge einer Liste.

Ausgabe:
Code:
?- kombinationen(100,Anzahl).
Anzahl = 4674.
kombinationen(90,Anzahl).
Anzahl = 2564.
?- kombinationen(50,Anzahl).
Anzahl = 115.
 
Ja ich versteh was du meinst aber vom Verständnis her meine ich da brauchst du bei meinem Programm nicht mal richtiger Programmierer zu sein um es zu checken
des halb hab ich es gesagt aber sonst sind die anderen doch nicht falsch im gegensatz ich fand einige von denen sogar sehr gut

LG
 
Dank CDW kann ich auch eine Lösung (Java) posten:

Code:
public class WeightInEuros {
	
	public static void main(String[] args) {
		System.out.println("Euro-Münzen Kombinationen die exat 100g ergeben!");
		System.out.println("Anzahl: "+ new WeightInEuros().new Combinator().getCounter());
	}
	
	class Combinator {
		
		private final int limit = 100*100;
		private final int[] coins = { 230, 306, 392, 410, 574, 780, 750, 850 };
		
		private int counter = 0;
		
		public Combinator() {
			doIt(0, 0);
		}
		
		private void doIt(int sum, int index) {
			if (sum == limit){
				counter++; 
				return;
			}
			if (sum > limit) {
				return;
			}
			if (sum < limit) {
				while (index < coins.length){
					int weight = sum + coins[index];
					doIt(weight, index);
					index++;
				}
			}
		}
		
		public int getCounter() {
			return counter;
		}
		
	}

}
 
Zurück
Oben