硬币交换算法

Question

我正在建立一个扑克游戏.在我的申请中,我有一堂课ChipSet.A ChipSet基本上是5个整数的数组(每个颜色扑克筹码一个).

public class ChipSet {

    public static final int WHITE_VALUE = 1;
    public static final int RED_VALUE = 2;
    public static final int GREEN_VALUE = 5;
    public static final int BLUE_VALUE = 10;
    public static final int BLACK_VALUE = 20;

    public static final int[] VALUES = new int[]{WHITE_VALUE, RED_VALUE, GREEN_VALUE, BLUE_VALUE, BLACK_VALUE};

    protected int[] chips;

    public ChipSet(int[] chips) {
        if (chips == null || chips.length != 5)
            throw new IllegalArgumentException("ChipSets should contain exactly 5 integers!");

        // store a copy of passed array
        this.chips = new int[5];
        for (int i = 0; i < this.chips.length; i++) {
            this.chips[i] = chips[i];
        }
    }

    public int getSum() {
        return chips[0] * WHITE_VALUE +
                chips[1] * RED_VALUE +
                chips[2] * GREEN_VALUE +
                chips[3] * BLUE_VALUE +
                chips[4] * BLACK_VALUE;
    }
}

现在如果我有ChipSet一个数组[0,0,2,1,0](5 + 5 + 10 = 20)并且我想用我ChipSet支付16个单位的东西.我不得不交换筹码才能做到这一点.

我需要的是一种尽可能高效交换的算法(交换尽可能少的筹码)以使这种支付成为可能.付款只会减去阵列中的筹码数量,因此剩余ChipSet的钱仍将在付款后.我该怎么做？

我需要的是这种方法:

public boolean exchangeToMakeAvailable(int goal) {
    // algorithm to exchange chips as efficient as possible

    // store the new values in the array, making sure the sum is still the same

    // return whether it has succeeded (false when the sum is less than the requested amount)
}

如果你能帮助我解决这个问题,我将非常感激.

例如:

在算法之前我有一个ChipSet,其数组[0,0,2,1,0]总和为20.我想支付16个单位的费用.在使用算法之后,我会尽可能地进行最有效的交换,在这种情况下,算法会将数组更改[1,2,1,1,0]为20的总和,但现在我可以支付16.付款之后,ChipSet将拥有阵列[0,2,0,0,0].

我希望我的问题很明确,如果不是,请发表评论,我会进一步解释.

Answer 1

这是一个编辑，我完全修改了我的答案。

\n\n

**从游戏角度来看的问题**\n玩家有 2 个绿色筹码（5 分）和 1 个蓝色筹码（10 分）。这总共是20分。现在玩家想要购买一个游戏内图标，需要花费 16 点。玩家有足够的钱来购买该物品。那么玩家支付了16点，但是他会给商店多少点才能正确支付。

\n\n

现在我已经编写了一个工作示例并完成了所有工作。

\n\n

代码

\n\n

程序.java

\n\n

import java.util.Arrays;\n\npublic class Program {\n\n    public static void main(String[] args) {\n        // Setting up test environment\n        Player player = new Player("Borrie", new int[]{0,0,0,0, 230});\n        int itemCost = 16626;\n        // Pay for item\n        System.out.printf("First we check if the player can pay with it\'s current ChipSet");\n        if (!player.canPayWithChipSet(player.getChips(), 5)) {\n            if (player.exchangeChips(5)) {\n                System.out.printf("\\n\\nThe players ChipSet:" + Arrays.toString(player.getChips().chips));\n                System.out.printf("\\nThe players ChipSet has been succesfully exchanged.");\n            } else {\n                System.out.printf("\\n\\nThe players ChipSet:" + Arrays.toString(player.getChips().chips));\n                System.out.printf("\\nThe players ChipSet was not able to be exchanged.\\n");\n            }\n        } else {\n            System.out.printf("\\n\\nThe player can pay exact with it\'s original ChipSet. No need to exchange.");\n        }\n\n    }\n}\n

\n\n

播放器.java

\n\n

    import java.util.ArrayList;\nimport java.util.Arrays;\n\npublic class Player {\n\n    private String name;\n    private ChipSet chips;\n    private int points = 0;\n\n    public Player(String name, int[] chips) {\n        this.name = name;\n        this.chips = new ChipSet(chips);\n        this.points = this.chips.getSum();\n    }\n\n    public boolean exchangeChips(int cost) {\n        ChipSet newChipSet = exchangePlayerChipSet(this.chips.getChips(), cost);\n        if (newChipSet == null) {\n            return false;\n        } else {\n            this.chips = newChipSet;\n            return true;\n        }\n    }\n\n    public ChipSet exchangePlayerChipSet(int[] originalChipValues, int cost) {\n        ChipSet newChipSet = null;\n        // Create possible combinations to compare\n        ArrayList<ChipSet> chipSetCombos = createCombinations(this.chips.getChips());\n        // Filter the chipset based on if it\'s able to pay without changing chips\n        System.out.printf("\\n\\n---- Filter which of these combinations are able to be payed with without changing chips ----");\n        ArrayList<ChipSet> filteredCombos = filterCombinations(chipSetCombos, cost);\n        // Compare the filtered chipsets to determine which one has changed the least\n        if (!filteredCombos.isEmpty()) {\n            newChipSet = compareChipSets(originalChipValues, filteredCombos);\n        }\n        return newChipSet;\n    }\n\n    private ArrayList<ChipSet> createCombinations(int[] array) {\n        ArrayList<ChipSet> combos = new ArrayList<>();\n        int[] startCombo = array;\n        System.out.printf("Player has " + getTotalPoints(startCombo) + " points in chips.");\n        System.out.printf("\\nPlayer has these chips (WHITE,RED,GREEN,BLUE,BLACK): " + Arrays.toString(startCombo));\n\n        while (startCombo[4] != 0) {\n            startCombo = lowerBlack(startCombo);\n            if (getTotalPoints(startCombo) == points) {\n                combos.add(new ChipSet(startCombo));\n            }\n        }\n        while (startCombo[3] != 0) {\n            startCombo = lowerBlue(startCombo);\n            if (getTotalPoints(startCombo) == points) {\n                combos.add(new ChipSet(startCombo));\n            }\n        }\n        while (startCombo[2] != 0) {\n            startCombo = lowerGreen(startCombo);\n            if (getTotalPoints(startCombo) == points) {\n                combos.add(new ChipSet(startCombo));\n            }\n        }\n        while (startCombo[1] != 0) {\n            startCombo = lowerRed(startCombo);\n            if (getTotalPoints(startCombo) == points) {\n                combos.add(new ChipSet(startCombo));\n            }\n        }\n        System.out.printf("\\n\\n---- Creating variations on the players chips ----");\n        System.out.printf("\\nVariation (all worth " + getTotalPoints(startCombo) + " points):\\n");\n        int teller = 1;\n        for (ChipSet a : combos) {\n            System.out.printf("\\nCombo " + teller + ": " + Arrays.toString(a.getChips()));\n            teller++;\n        }\n        return combos;\n    }\n\n    private ArrayList<ChipSet> filterCombinations(ArrayList<ChipSet> combinations, int cost) {\n        ArrayList<ChipSet> filteredChipSet = new ArrayList<>();\n        combinations.stream().filter((cs) -> (canPayWithChipSet(cs, cost))).forEach((cs) -> {\n            filteredChipSet.add(cs);\n        });\n        return filteredChipSet;\n    }\n\n    // This method has be worked out\n    public boolean canPayWithChipSet(ChipSet cs, int cost) {\n        ChipSet csOrig = new ChipSet(cs.chips);\n        ChipSet csCopy = new ChipSet(cs.chips);\n        int counterWhite = 0;\n        int counterRed = 0;\n        int counterGreen = 0;\n        int counterBlue = 0;\n        int counterBlack = 0;\n\n        while (20 <= cost && cost > 0 && csOrig.getChips()[4] != 0) {\n            csOrig.getChips()[4] -= 1;\n            cost -= 20;\n            counterBlack++;\n        }\n        while (10 <= cost && cost > 0 && csOrig.getChips()[3] != 0) {\n            csOrig.getChips()[3] -= 1;\n            cost -= 10;\n            counterBlue++;\n        }\n        while (5 <= cost && cost > 0 && csOrig.getChips()[2] != 0) {\n            csOrig.getChips()[2] -= 1;\n            cost -= 5;\n            counterGreen++;\n        }\n        while (2 <= cost && cost > 0 && csOrig.getChips()[1] != 0) {\n            csOrig.getChips()[1] -= 1;\n            cost -= 2;\n            counterRed++;\n        }\n        while (1 <= cost && cost > 0 && csOrig.getChips()[0] != 0) {\n            csOrig.getChips()[0] -= 1;\n            cost -= 1;\n            counterWhite++;\n        }\n        if (cost == 0){\n            System.out.printf("\\nCombo: %s can pay exact. With %d white, %d red, %d green, %d blue an %d black chips", Arrays.toString(csCopy.chips),counterWhite,counterRed,counterGreen,counterBlue,counterBlack);\n            return true;\n        } else {\n            System.out.printf("\\nCombo: %s cannot pay exact.\\n\\n\\n", Arrays.toString(csCopy.chips));\n            return false;\n        }    \n    }\n\n    private ChipSet compareChipSets(int[] originalChipValues, ArrayList<ChipSet> chipSetCombos) {\n        ChipSet newChipSet;\n        int[] chipSetWaardes = originalChipValues; // originele chipset aantal van kleur\n        int[] chipSetCombosDifferenceValues = new int[chipSetCombos.size()];\n        int teller = 1;\n\n        System.out.printf("\\n\\n---- Calculate differences between players stack and it\'s variations ----");\n        for (ChipSet cs : chipSetCombos) {\n            int aantalWhite = cs.getChips()[0];\n            int aantalRed = cs.getChips()[1];\n            int aantalGreen = cs.getChips()[2];\n            int aantalBlue = cs.getChips()[3];\n            int aantalBlack = cs.getChips()[4];\n            int differenceWhite = Math.abs(chipSetWaardes[0] - aantalWhite);\n            int differenceRed = Math.abs(chipSetWaardes[1] - aantalRed);\n            int differenceGreen = Math.abs(chipSetWaardes[2] - aantalGreen);\n            int differenceBlue = Math.abs(chipSetWaardes[3] - aantalBlue);\n            int differenceBlack = Math.abs(chipSetWaardes[4] - aantalBlack);\n            int totalDifference = differenceWhite + differenceRed + differenceGreen + differenceBlue + differenceBlack;\n            chipSetCombosDifferenceValues[teller - 1] = totalDifference;\n            System.out.printf("\\nCombo " + teller + ": " + Arrays.toString(cs.getChips()) + " = " + totalDifference);\n            teller++;\n        }\n        newChipSet = chipSetCombos.get(smallestValueOfArrayIndex(chipSetCombosDifferenceValues));\n        System.out.printf("\\n\\nThe least different ChipSet is: " + Arrays.toString(newChipSet.getChips()) + " ");\n        return newChipSet;\n    }\n\n    private int smallestValueOfArrayIndex(int[] array) {\n        int huidigeWaarde = array[0];\n        int smallestIndex = 0;\n        for (int j = 1; j < array.length; j++) {\n            if (array[j] < huidigeWaarde) {\n                huidigeWaarde = array[j];\n                smallestIndex = j;\n            }\n        }\n        return smallestIndex;\n    }\n\n    private int[] lowerBlack(int[] array) {\n        return new int[]{array[0], array[1], array[2], array[3] + 2, array[4] - 1};\n    }\n\n    private int[] lowerBlue(int[] array) {\n        return new int[]{array[0], array[1], array[2] + 2, array[3] - 1, array[4]};\n    }\n\n    private int[] lowerGreen(int[] array) {\n        return new int[]{array[0] + 1, array[1] + 2, array[2] - 1, array[3], array[4]};\n    }\n\n    private int[] lowerRed(int[] array) {\n        return new int[]{array[0] + 2, array[1] - 1, array[2], array[3], array[4]};\n    }\n\n    private int getTotalPoints(int[] array) {\n        return ((array[0] * 1) + (array[1] * 2) + (array[2] * 5) + (array[3] * 10) + (array[4] * 20));\n    }\n\n    public String getName() {\n        return this.name;\n    }\n\n    public int getPoints() {\n        return this.points;\n    }\n\n    public ChipSet getChips() {\n        return chips;\n    }\n\n}\n

\n\n

芯片组.java

\n\n

public class ChipSet {\n\n    public static final int WHITE_VALUE = 1;\n    public static final int RED_VALUE = 2;\n    public static final int GREEN_VALUE = 5;\n    public static final int BLUE_VALUE = 10;\n    public static final int BLACK_VALUE = 20;\n\n    public static final int[] VALUES = new int[]{WHITE_VALUE, RED_VALUE, GREEN_VALUE, BLUE_VALUE, BLACK_VALUE};\n\n    protected int[] chips;\n\n    public ChipSet(int[] chips) {\n        if (chips == null || chips.length != 5) {\n            throw new IllegalArgumentException("ChipSets should contain exactly 5 integers!");\n        }\n\n        // store a copy of passed array\n        this.chips = new int[5];\n        for (int i = 0; i < this.chips.length; i++) {\n            this.chips[i] = chips[i];\n        }\n    }\n\n    public int getSum() {\n        return chips[0] * WHITE_VALUE\n                + chips[1] * RED_VALUE\n                + chips[2] * GREEN_VALUE\n                + chips[3] * BLUE_VALUE\n                + chips[4] * BLACK_VALUE;\n    }\n\n    public int[] getChips() {\n        return this.chips;\n    }\n}\n

\n\n

一些解释：

\n\n

\n
• 创建组合
\n

\n\n

\n

我们创建了一些子方法，将芯片换成较低的芯片。例如，黑色 = 2 蓝色。然后我们按顺序创建 5 个循环。\n 第一个检查是否还有黑色芯片，如果有，则减少 1 个黑色\n 添加 2 个蓝色。如果新 ChipSet 中的 Chip 总和等于原始 ChipSets 值，则将此新组合保存在列表中。循环继续，直到不再有黑人为止。然后它检查是否有蓝色，并重复相同的过程，直到不再有红色。现在我们列出了芯片中 X 值的所有可能变化。

\n

\n\n

\n
• 过滤器组合
\n

\n\n

\n

您可以根据\n 是否可以用芯片组支付 X 积分而不进行交换来过滤芯片组。我们循环遍历上一部分中创建的芯片组的所有可能组合。如果您可以使用芯片组进行支付而无需交换，则将其添加到芯片组的过滤列表中。结果是仅包含有效芯片组的归档列表。

\n

\n\n

\n
• 计算差异
\n

\n\n

\n

对于每个芯片组，我们计算芯片组中所有颜色的芯片数量，并用它减去原始芯片组的芯片数量。\n 取其绝对值，并对原始芯片组的所有差异进行求和。和组合颜色。现在我们有了一个代表与原始值的差异的数字。现在我们所要做的就是比较所有芯片组\xc2\xb4的差异数\xc2\xb4。我们用来分配给玩家的差异最小的一个。

\n

\n\n

简单呵呵

\n