Ein Narr lernt Java

[Peregrin_Tooc]

reicht aber auch noch nicht. da passiert immer noch Blödsinn

[Tzu Iop]

Post mal deinen aktuellen Code und die Fehlermeldung, dann ist es einfacher zu helfen. Sonst kann ich jetzt nur wild rum raten.

[Peregrin_Tooc]

Das werd ich nachher mal machen, vorher muss der aber noch ein bisschen verschönert und kommentiert werden...

[Tzu Iop]

Um schon mal eine Vermutung zu äußern:

A a1 = new A(1,2);
A a2 = new A(1,2);
HashMap<A, Integer> m = new HashMap<A, Integer>();
m.put(a1, 1);
System.out.println(m.get(a2)); 

Die Rückgabe ist null. Was du vermutlich willst, ist eine TreeMap.

[Peregrin_Tooc]

Code:

public static BigInteger possibleCombinations(BigInteger amount, Vector<BigInteger> coins, HashMap<Vector<Object>, BigInteger> cache){
        System.out.println("remaining coins: "+coins+", amount: "+amount+" Cache: "+cache); //for debugging only
        int l = coins.size(); 
        //what is the sum of the remaining coins?
        BigInteger sumOfCoins = BigInteger.ZERO;
        for(BigInteger coin : coins){
            sumOfCoins = sumOfCoins.add(coin);
        }
        // if the sum of coins is smaller than the amount of money to be given out, there is no way of doing this
        if(amount.compareTo(sumOfCoins)>0){
            return BigInteger.ZERO;
        }
        // if the sum of coins equals the amount of money to be given out, there is exactly one way of doing this
        if(amount.equals(sumOfCoins)){
            return BigInteger.ONE;
        }
        // if there is no money to be given out, there is no way of doing this, this includes negative amounts
        if(amount.compareTo(BigInteger.ZERO)<=0){
            return BigInteger.ZERO;
        }
        //if there are no more coins, we can't give out any money!
        if(coins.size()==0){
            return BigInteger.ZERO;
        }
        //now we check if the number of combinations have already been calculated for the parameters in question 
        Vector<Object> key1 = new Vector<Object>(Arrays.asList(new Object[]{amount, coins}));
        BigInteger solution = cache.get(key1); 
        if(solution != null){
            return solution;
        }
        //if the number of combinations for amount n and the coins {a_1,...,a_m} has not been calculated yet, we note this number f(n,{a_1,...,a_m}), we can calculate it as f(n,{a_1,...,a_(m-1)})+f(n-a_m,{a_1,...,a_(m-1)}) 
        BigInteger reducedAmount = amount.subtract(coins.get(l-1)); 
        Vector<BigInteger> reducedCoins1 = (Vector<BigInteger>) coins.clone();
        reducedCoins1.remove(l-1);
        Vector<BigInteger> reducedCoins2 = (Vector<BigInteger>) coins.clone();
        reducedCoins2.remove(l-1);
        Vector<Object> key2 = new Vector<Object>(Arrays.asList(new Object[]{amount, reducedCoins1})); 
        Vector<Object> key3 = new Vector<Object>(Arrays.asList(new Object[]{reducedAmount, reducedCoins2})); 
        BigInteger possibilites2 = possibleCombinations(amount, reducedCoins1, cache); //calculate f(n,{a_1,...,a_(m-1)})
        BigInteger possibilites3 = possibleCombinations(reducedAmount, reducedCoins2, cache); //calculate f(n-a_m,{a_1,...,a_(m-1)})
        //we put both summands in the cache
        cache.put(key2,possibilites2);
        cache.put(key3, possibilites3);
        //f(n,{a_1,...,a_(m-1)})+f(n-a_m,{a_1,...,a_(m-1)}) 
        BigInteger possibilities = possibilites2.add(possibilites3);
        return possibilities;
    } 

Ausgabe mit Parametern amount = 10, coins ={1,1,2,2,4,4,8,8}:

remaining coins: [1, 1, 2, 2, 4, 4, 8, 8], amount: 10 Cache: {}
remaining coins: [1, 1, 2, 2, 4, 4, 8], amount: 10 Cache: {}
remaining coins: [1, 1, 2, 2, 4, 4], amount: 10 Cache: {}
remaining coins: [1, 1, 2, 2, 4], amount: 10 Cache: {}
remaining coins: [1, 1, 2, 2, 4], amount: 6 Cache: {}
remaining coins: [1, 1, 2, 2], amount: 6 Cache: {}
remaining coins: [1, 1, 2, 2], amount: 2 Cache: {}
remaining coins: [1, 1, 2], amount: 2 Cache: {}
remaining coins: [1, 1], amount: 2 Cache: {}
remaining coins: [1, 1], amount: 0 Cache: {}
remaining coins: [1, 1, 2], amount: 0 Cache: {[2, [1, 1]]=1, [0, [1, 1]]=0}
remaining coins: [1, 1, 2, 2, 4, 4], amount: 2 Cache: {[2, [1, 1]]=1, [6, [1, 1, 2, 2, 4]]=2, [6, [1, 1, 2, 2]]=1, [0, [1, 1]]=0, [10, [1, 1, 2, 2, 4]]=1, [2, [1, 1, 2]]=1, [0, [1, 1, 2]]=0, [2, [1, 1, 2, 2]]=1}
remaining coins: [1, 1, 2, 2, 4], amount: 2 Cache: {[2, [1, 1]]=1, [6, [1, 1, 2, 2, 4]]=2, [6, [1, 1, 2, 2]]=1, [0, [1, 1]]=0, [10, [1, 1, 2, 2, 4]]=1, [2, [1, 1, 2]]=1, [0, [1, 1, 2]]=0, [2, [1, 1, 2, 2]]=1}
remaining coins: [1, 1, 2, 2], amount: 2 Cache: {[2, [1, 1]]=1, [6, [1, 1, 2, 2, 4]]=2, [6, [1, 1, 2, 2]]=1, [0, [1, 1]]=0, [10, [1, 1, 2, 2, 4]]=1, [2, [1, 1, 2]]=1, [0, [1, 1, 2]]=0, [2, [1, 1, 2, 2]]=1}
remaining coins: [1, 1, 2, 2], amount: -2 Cache: {[2, [1, 1]]=1, [6, [1, 1, 2, 2, 4]]=2, [6, [1, 1, 2, 2]]=1, [0, [1, 1]]=0, [10, [1, 1, 2, 2, 4]]=1, [2, [1, 1, 2]]=1, [0, [1, 1, 2]]=0, [2, [1, 1, 2, 2]]=1}
remaining coins: [1, 1, 2, 2, 4], amount: -2 Cache: {[2, [1, 1]]=1, [-2, [1, 1, 2, 2]]=0, [6, [1, 1, 2, 2, 4]]=2, [6, [1, 1, 2, 2]]=1, [0, [1, 1]]=0, [10, [1, 1, 2, 2, 4]]=1, [2, [1, 1, 2]]=1, [0, [1, 1, 2]]=0, [2, [1, 1, 2, 2]]=1}
remaining coins: [1, 1, 2, 2, 4, 4, 8], amount: 2 Cache: {[6, [1, 1, 2, 2, 4]]=2, [2, [1, 1, 2, 2, 4, 4]]=1, [10, [1, 1, 2, 2, 4, 4]]=3, [2, [1, 1]]=1, [-2, [1, 1, 2, 2]]=0, [-2, [1, 1, 2, 2, 4]]=0, [0, [1, 1]]=0, [6, [1, 1, 2, 2]]=1, [2, [1, 1, 2, 2, 4]]=1, [10, [1, 1, 2, 2, 4]]=1, [2, [1, 1, 2]]=1, [0, [1, 1, 2]]=0, [2, [1, 1, 2, 2]]=1}
remaining coins: [1, 1, 2, 2, 4, 4], amount: 2 Cache: {[6, [1, 1, 2, 2, 4]]=2, [2, [1, 1, 2, 2, 4, 4]]=1, [10, [1, 1, 2, 2, 4, 4]]=3, [2, [1, 1]]=1, [-2, [1, 1, 2, 2]]=0, [-2, [1, 1, 2, 2, 4]]=0, [0, [1, 1]]=0, [6, [1, 1, 2, 2]]=1, [2, [1, 1, 2, 2, 4]]=1, [10, [1, 1, 2, 2, 4]]=1, [2, [1, 1, 2]]=1, [0, [1, 1, 2]]=0, [2, [1, 1, 2, 2]]=1}
remaining coins: [1, 1, 2, 2, 4, 4], amount: -6 Cache: {[6, [1, 1, 2, 2, 4]]=2, [2, [1, 1, 2, 2, 4, 4]]=1, [10, [1, 1, 2, 2, 4, 4]]=3, [2, [1, 1]]=1, [-2, [1, 1, 2, 2]]=0, [-2, [1, 1, 2, 2, 4]]=0, [0, [1, 1]]=0, [6, [1, 1, 2, 2]]=1, [2, [1, 1, 2, 2, 4]]=1, [10, [1, 1, 2, 2, 4]]=1, [2, [1, 1, 2]]=1, [0, [1, 1, 2]]=0, [2, [1, 1, 2, 2]]=1} 

Edit:

Um schon mal eine Vermutung zu äußern:

A a1 = new A(1,2);
A a2 = new A(1,2);
HashMap<A, Integer> m = new HashMap<A, Integer>();
m.put(a1, 1);
System.out.println(m.get(a2)); 

Die Rückgabe ist null. Was du vermutlich willst, ist eine TreeMap.

Das könnte zwar sein, glaube ich aber nicht:

public static void main(String[] args) {
        HashMap<Vector<Long>,Long> map = new HashMap<Vector<Long>, Long>();
        Long[] arr1 = {1L,2L};
        Long[] arr2 = {1L,2L};
        Vector<Long> vec1 = new Vector<Long>(Arrays.asList(arr1));
        Vector<Long> vec2 = new Vector<Long>(Arrays.asList(arr2));
        map.put(vec1, 1L);
        System.out.println(map.get(vec2));
    }

} 

Rückgabe ist 1.

[Peregrin_Tooc]

Nachtrag:

Die Cache-Werte sind halt schwachsinnig, das ist der Ärger. [6, [1, 1, 2, 2, 4]]=2 z.B. ist Blödsinn, f(2,{1,1,2,2,4})=3 (nämlich 6 = 4+2 = 4+1+1 = 2+2+1+1)

[Tzu Iop]

Nachtrag:

Die Cache-Werte sind halt schwachsinnig, das ist der Ärger. [6, [1, 1, 2, 2, 4]]=2 z.B. ist Blödsinn, f(2,{1,1,2,2,4})=3 (nämlich 6 = 4+2 = 4+1+1 = 2+2+1+1)

Er findet bei amount = 2 nur die Lösung 1+1, wenn ich das richtig sehe. Kann dir aber nicht sagen, woran das liegt.

[Peregrin_Tooc]

Hmmm... spannend.

Es ist irgendwo klar, woran das liegt. Man fängt mit 2 und (1,1,2) an. Da trifft keines der Abbruchkriterien zu. Also wird 2,(1,1) berechnet, das ist 1. Dann wird 0,(1,1) berechnet, was nach Abbruchkriterium 0 ist. Das ist aber nicht gut, weil da ja eine Möglichkeit weggenommen wird! Wenn man aber Grundsätzlich bei amount = 0 ein return 1 macht, dann passiert auch wieder Blödsinn, weil er ja mit dem reducedAmount auf jeden Fall noch weiter rechnet. Ich denke die Lösung ist, sofort nach der Reduzierung zu prüfen, ob es bei 0 landet und in dem Fall die Anzahl der Möglichkeiten zu erhöhen.

[alpha civ]

Schau dir mal den Fall an:

        if(amount.compareTo(BigInteger.ZERO)<=0){
            return BigInteger.ZERO; 

Das "<=" ist falsch, es muss nur "<" sein. Ich habe es getestet (mit Python), und dann klappt es. Bei amount=2, coins={1,1,2} liefert er mir dann zwei Möglichkeiten.

Edit: Zu langsam....

[Peregrin_Tooc]

Mach mal amount = 2, coins = 1,1,2,2... dann liefert er Dir bestimmt drei

[alpha civ]

Was ja auch logisch ist, da man zwei verschiedene 2-Münzen hat.
Wenn man sowas nicht haben will, braucht man wahrscheinlich eine andere Datenstruktur für coins als eine Liste.

[Tzu Iop]

Die Aufgabe an sich ist ja schon durchaus schwierig. Wobei mich interessieren würde, ob vorgegeben ist, dass es von jeder Art nur genau zwei Münzen gibt. Ich hab es mal für den Fall, dass man von einer Art beliebig viele Münzen benutzen kann in Prolog geschrieben, da ist das um Welten einfacher.

[Peregrin_Tooc]

@alpha civ: Oh verdammt. Ja, das ist natürlich richtig Dann muss man wahrscheinlich nachhalten, wie oft man eine Münze verwendet und wenn sie ein drittes mal verwendet werden soll, muss 0 ausgegeben werden.

@TzuIop: es ist vorgegeben, dass man jede Münze maximal zwei mal benutzen darf. Für den Fall, dass man jeden Münze so oft verwenden darf wie man will, ist es tatsächlich weitaus einfacher.

[c4master]

Oha, da musst du aber nochmal richtig Gehirnschmalz reinstecken. Das klingt nach einem relativ üblen Problem...

edit: Gibt es "Multimengen" in Java? Das wäre vielleicht die Lösung.

[Peregrin_Tooc]

Klar gibt es Multimengen, eine Menge von Mengen halt

Ich bin gerade dran, ohne Multimengen, mal schauen, ob ich das jetzt hinbekomme