Greedy Algorithmusas in an example in a card game

Question

You play a new trading card game. You and the computer each have a card- Deck. The computer lays a card, then you lay your card. Each card has a Strength value, with the card with the higher strength value winning. If you and the If computers have equally strong cards, the computer wins. You know the cards of the computer. Your goal is to calculate the sum of the strength values of your Maximize cards that have won. For this you get two integer arrays which represent your cards and those of the computer.

You would have the cards [5, 15, 100, 1, 5]. The computer uses the same cards, so also [5, 15, 100, 1, 5]. When the computer places its 100, you place Your 1, since you cannot win. If he lays his 15, you lay your 100 and have won. If he lays his 5, then lay your 15th. If he lays his second 5, then lay you get your 5 and lose this round. If he puts his 1, you counter with your 5th total. you will get winning cards worth 120.

Task: Describe your greedy algorithm idea that can calculate the sum.

My algorithm: When the computer places the largest card from its deck (in this case 100) I place the smallest number in my case the 1. I would go on with this and at the i would write whenever I win add the result

Has anybody another suggestions for the greedy algorithm

Answer 1

Your idea is correct. There is also another point to think about here.

For [5, 15, 100, 1, 5],

1. Computer throws 5 and you throw 100 because it is largest.
2. Next computer throws 15, now the maximum you have is 15 and you would lose the point.

To avoid this, you should choose the next maximum to the given number.

1. When the computer throws 5, you throw 15.
2. When the computer throws 15, you throw 100 and get the point.

If all the cards are unique you could win (n-1) points this way where n is the size of the array.

So, the algorithm would be to find the next maximum. If it is possible to find it, return it or else return the smallest number in the array.