मैं जावा में गतिशील प्रोग्रामिंग के साथ एक कार्य कर रहा हूं और मैं फंस गया: कार्य में हमें यादृच्छिक संख्या में चट्टानों के साथ बाल्टी की एक सरणी दी जाती है, जहां दोनों खिलाड़ी शुरू से ही अपनी राशि जानते हैं। खिलाड़ी भ्रमण करते हैं और किनारों से एक बॉर्डर बकेट चुनते हैं:

बाल्टी: (3)(3)(8)(2)(10)(4)

P1: (3) बाल्टी शेष: (3)(8)(2)(10)(4),

P2:(4) बाल्टियाँ शेष: (3)(8)(2)(10),

P1:(10) बाल्टी शेष: (3)(8)(2),

P2(3) बकेट बाकी: (8)(2),

P1:(8) बाल्टियाँ शेष (2),

P2:(2) अंत

अंतिम स्कोर की गणना (खिलाड़ी 1 की चट्टानें) के साथ की जाती है - (खिलाड़ी 2 की चट्टानें)

स्कोर = (3+10+8)-(4+3+2) = 12

हम खिलाड़ी 1 खेलते हैं और हमारा लक्ष्य इष्टतम पिक ऑर्डर ढूंढना है जिसमें हमारा सबसे बड़ा स्कोर है।

मैं डीपी की अवधारणा को जानता हूं लेकिन मुझे नहीं पता कि मैं समय को बेहतर बनाने के लिए क्या बचा सकता हूं। कोड का मुख्य भाग मैंने मिनमैक्स एल्गोरिदम के साथ किया था और यह काम करता था लेकिन मुझे नहीं पता कि इसे गतिशील प्रोग्रामिंग के साथ कैसे जोड़ा जाए

मैंने पंक्तियों के साथ एक मैट्रिक्स को बाईं ओर से बाल्टी के रूप में और कॉलम को दाईं ओर से बाल्टी के रूप में रखने की कोशिश की, इसलिए जब हम सरणी के समान "भाग" का उपयोग करते हैं, तो मैं वहां उत्तर सहेज सकता हूं, लेकिन मुझे इसके साथ कुछ समस्याएं थीं ...

EDIT1: मेरा कोड जोड़ा

public int maxGain(int[] values)
{
    this.moves = new int[values.length+1][values.length+1];
    return  _maxGain(values,0,values.length-1,0,0,values.length,true,0,0);
}

public int _maxGain(int[] values, int leftBowl, int rightBowl, int valuePlayer1, int valuePlayer2,int leftBowls, boolean ifFirstPlayer, int leftMoves, int rightMoves){
        //Check if end of the game
        if(leftBowls == 0) {
            //Calculate the final score
            return valuePlayer1 - valuePlayer2;
        }
        //System.out.println("Left:"+values[leftBowl]+", right: "+values[rightBowl]);
        // If first player
        if(ifFirstPlayer){
            int maxEval = Integer.MIN_VALUE;
            int eval;
            for(int i=0;i<2;i++){
                if(i==0){
                    //Do move
                    valuePlayer1 = valuePlayer1+values[leftBowl];
                    leftBowls--;
                    leftMoves++;
                    if(moves[leftMoves][rightMoves] != 0){
                        eval = moves[leftMoves][rightMoves];
                        System.out.println("USED! Left:"+leftMoves+",right: "+rightMoves+" Moves: " + moves[leftMoves][rightMoves] );
                    }else {
                        eval = _maxGain(values, leftBowl + 1, rightBowl, valuePlayer1, valuePlayer2, leftBowls, false, leftMoves, rightMoves);
                        moves[leftMoves][rightMoves] = eval;
                        System.out.println("Left:"+leftMoves+",right: "+rightMoves+" Moves: " + moves[leftMoves][rightMoves] );
                        for(int x=0;x<this.moves.length;x++){
                            for(int j=0;j<this.moves.length;j++){
                                System.out.print(this.moves[x][j]+" ");
                            }
                            System.out.println();
                        }
                    }
                    leftMoves--;
                    maxEval = Math.max(maxEval,eval);
                    //Undo move
                    valuePlayer1 = valuePlayer1-values[leftBowl];
                    leftBowls++;
                }else{
                    //Do move
                    valuePlayer1 = valuePlayer1+values[rightBowl];
                    leftBowls--;
                    rightMoves++;
                    if(moves[leftMoves][rightMoves] != 0){
                        eval = moves[leftMoves][rightMoves];
                        System.out.println("USED! Left:"+leftMoves+",right: "+rightMoves+" Moves: " + moves[leftMoves][rightMoves] );
                    }else {
                        eval = _maxGain(values, leftBowl, rightBowl - 1, valuePlayer1, valuePlayer2, leftBowls, false, leftMoves, rightMoves);
                        moves[leftMoves][rightMoves] = eval;
                        System.out.println("Left:"+leftMoves+",right: "+rightMoves+" Moves: " + moves[leftMoves][rightMoves] );
                        for(int x=0;x<this.moves.length;x++){
                            for(int j=0;j<this.moves.length;j++){
                                System.out.print(this.moves[x][j]+" ");
                            }
                            System.out.println();
                        }
                    }
                    rightMoves--;
                    maxEval = Math.max(maxEval,eval);
                    //Undo move
                    valuePlayer1 = valuePlayer1-values[rightBowl];
                    leftBowls++;
                }
            }
            return maxEval;
            //If second player
        }else{
            int minEval = Integer.MAX_VALUE;
            int eval;
            for(int i=0;i<2;i++){
                if(i==0){
                    //Do move
                    valuePlayer2 = valuePlayer2+values[leftBowl];
                    leftBowls--;
                    leftMoves++;
                    if(moves[leftMoves][rightMoves] != 0){
                        eval = moves[leftMoves][rightMoves];
                        System.out.println("USED! Left:"+leftMoves+",right: "+rightMoves+" Moves: " + moves[leftMoves][rightMoves] );
                    }else {
                        eval = _maxGain(values, leftBowl + 1, rightBowl, valuePlayer1, valuePlayer2, leftBowls, true, leftMoves, rightMoves);
                        moves[leftMoves][rightMoves] = eval;
                        System.out.println("Left:"+leftMoves+",right: "+rightMoves+" Moves: " + moves[leftMoves][rightMoves] );
                        for(int x=0;x<this.moves.length;x++){
                            for(int j=0;j<this.moves.length;j++){
                                System.out.print(this.moves[x][j]+" ");
                            }
                            System.out.println();
                        }
                    }
                    leftMoves--;
                    minEval = Math.min(minEval,eval);
                    //Undo move
                    valuePlayer2 = valuePlayer2-values[leftBowl];
                    leftBowls++;
                }else{
                    //Do move
                    valuePlayer2 = valuePlayer2+values[rightBowl];
                    leftBowls--;
                    rightMoves++;
                    if(moves[leftMoves][rightMoves] != 0){
                        eval = moves[leftMoves][rightMoves];
                        System.out.println("USED! Left:"+leftMoves+",right: "+rightMoves+" Moves: " + moves[leftMoves][rightMoves] );
                    }else {
                        eval = _maxGain(values, leftBowl, rightBowl - 1, valuePlayer1, valuePlayer2, leftBowls, true, leftMoves, rightMoves);
                        moves[leftMoves][rightMoves] = eval;
                        System.out.println("Left:"+leftMoves+",right: "+rightMoves+" Moves: " + moves[leftMoves][rightMoves] );
                        for(int x=0;x<this.moves.length;x++){
                            for(int j=0;j<this.moves.length;j++){
                                System.out.print(this.moves[x][j]+" ");
                            }
                            System.out.println();
                        }
                    }
                    rightMoves--;
                    minEval = Math.min(minEval,eval);
                    //Undo move
                    valuePlayer2 = valuePlayer2-values[rightBowl];
                    leftBowls++;
                }
            }
            return minEval;
        }
    }
0
Corgam 2 जून 2019, 00:10

1 उत्तर

सबसे बढ़िया उत्तर

ठीक है, इसलिए मुझे इस प्रकार के कार्य के लिए जीथब पर कोड मिला है, मैं इसे अन्य लोगों के लिए छोड़ दूंगा यदि उन्हें बाद में इसकी आवश्यकता है:

https://github.com/mission-peace/interview/blob/master/src/com/interview/dynamic/NPotGold.java?fbclid=IwAR2PZ8MvNJcQmlU13wj1n_c6m1UhQY7FXAY07RwaI6wOOXAMgDOVRxFahD0

0
Corgam 2 जून 2019, 22:25