java - 代币兑换算法

Question

我正在开发一款扑克游戏。在我的应用程序中，我有一个类 ChipSet。 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)
}

如果你能帮我解决这个问题，我将不胜感激。

例如:

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

我希望我的问题很清楚，如果没有，请发表评论，我会进一步解释。

Answer 1

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

**游戏角度的问题**玩家有 2 个绿色筹码(5 分)和 1 个蓝色筹码(10 分)。这总计20分。现在玩家想要购买一个值(value) 16 点的游戏内图标。玩家有足够的钱购买元素。所以玩家支付了16个积分，但是他会给店铺多少积分才能正确支付。

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

代码

程序.java

import java.util.Arrays;

public class Program {

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

    }
}

播放器.java

    import java.util.ArrayList;
import java.util.Arrays;

public class Player {

    private String name;
    private ChipSet chips;
    private int points = 0;

    public Player(String name, int[] chips) {
        this.name = name;
        this.chips = new ChipSet(chips);
        this.points = this.chips.getSum();
    }

    public boolean exchangeChips(int cost) {
        ChipSet newChipSet = exchangePlayerChipSet(this.chips.getChips(), cost);
        if (newChipSet == null) {
            return false;
        } else {
            this.chips = newChipSet;
            return true;
        }
    }

    public ChipSet exchangePlayerChipSet(int[] originalChipValues, int cost) {
        ChipSet newChipSet = null;
        // Create possible combinations to compare
        ArrayList<ChipSet> chipSetCombos = createCombinations(this.chips.getChips());
        // Filter the chipset based on if it's able to pay without changing chips
        System.out.printf("\n\n---- Filter which of these combinations are able to be payed with without changing chips ----");
        ArrayList<ChipSet> filteredCombos = filterCombinations(chipSetCombos, cost);
        // Compare the filtered chipsets to determine which one has changed the least
        if (!filteredCombos.isEmpty()) {
            newChipSet = compareChipSets(originalChipValues, filteredCombos);
        }
        return newChipSet;
    }

    private ArrayList<ChipSet> createCombinations(int[] array) {
        ArrayList<ChipSet> combos = new ArrayList<>();
        int[] startCombo = array;
        System.out.printf("Player has " + getTotalPoints(startCombo) + " points in chips.");
        System.out.printf("\nPlayer has these chips (WHITE,RED,GREEN,BLUE,BLACK): " + Arrays.toString(startCombo));

        while (startCombo[4] != 0) {
            startCombo = lowerBlack(startCombo);
            if (getTotalPoints(startCombo) == points) {
                combos.add(new ChipSet(startCombo));
            }
        }
        while (startCombo[3] != 0) {
            startCombo = lowerBlue(startCombo);
            if (getTotalPoints(startCombo) == points) {
                combos.add(new ChipSet(startCombo));
            }
        }
        while (startCombo[2] != 0) {
            startCombo = lowerGreen(startCombo);
            if (getTotalPoints(startCombo) == points) {
                combos.add(new ChipSet(startCombo));
            }
        }
        while (startCombo[1] != 0) {
            startCombo = lowerRed(startCombo);
            if (getTotalPoints(startCombo) == points) {
                combos.add(new ChipSet(startCombo));
            }
        }
        System.out.printf("\n\n---- Creating variations on the players chips ----");
        System.out.printf("\nVariation (all worth " + getTotalPoints(startCombo) + " points):\n");
        int teller = 1;
        for (ChipSet a : combos) {
            System.out.printf("\nCombo " + teller + ": " + Arrays.toString(a.getChips()));
            teller++;
        }
        return combos;
    }

    private ArrayList<ChipSet> filterCombinations(ArrayList<ChipSet> combinations, int cost) {
        ArrayList<ChipSet> filteredChipSet = new ArrayList<>();
        combinations.stream().filter((cs) -> (canPayWithChipSet(cs, cost))).forEach((cs) -> {
            filteredChipSet.add(cs);
        });
        return filteredChipSet;
    }

    // This method has be worked out
    public boolean canPayWithChipSet(ChipSet cs, int cost) {
        ChipSet csOrig = new ChipSet(cs.chips);
        ChipSet csCopy = new ChipSet(cs.chips);
        int counterWhite = 0;
        int counterRed = 0;
        int counterGreen = 0;
        int counterBlue = 0;
        int counterBlack = 0;

        while (20 <= cost && cost > 0 && csOrig.getChips()[4] != 0) {
            csOrig.getChips()[4] -= 1;
            cost -= 20;
            counterBlack++;
        }
        while (10 <= cost && cost > 0 && csOrig.getChips()[3] != 0) {
            csOrig.getChips()[3] -= 1;
            cost -= 10;
            counterBlue++;
        }
        while (5 <= cost && cost > 0 && csOrig.getChips()[2] != 0) {
            csOrig.getChips()[2] -= 1;
            cost -= 5;
            counterGreen++;
        }
        while (2 <= cost && cost > 0 && csOrig.getChips()[1] != 0) {
            csOrig.getChips()[1] -= 1;
            cost -= 2;
            counterRed++;
        }
        while (1 <= cost && cost > 0 && csOrig.getChips()[0] != 0) {
            csOrig.getChips()[0] -= 1;
            cost -= 1;
            counterWhite++;
        }
        if (cost == 0){
            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);
            return true;
        } else {
            System.out.printf("\nCombo: %s cannot pay exact.\n\n\n", Arrays.toString(csCopy.chips));
            return false;
        }    
    }

    private ChipSet compareChipSets(int[] originalChipValues, ArrayList<ChipSet> chipSetCombos) {
        ChipSet newChipSet;
        int[] chipSetWaardes = originalChipValues; // originele chipset aantal van kleur
        int[] chipSetCombosDifferenceValues = new int[chipSetCombos.size()];
        int teller = 1;

        System.out.printf("\n\n---- Calculate differences between players stack and it's variations ----");
        for (ChipSet cs : chipSetCombos) {
            int aantalWhite = cs.getChips()[0];
            int aantalRed = cs.getChips()[1];
            int aantalGreen = cs.getChips()[2];
            int aantalBlue = cs.getChips()[3];
            int aantalBlack = cs.getChips()[4];
            int differenceWhite = Math.abs(chipSetWaardes[0] - aantalWhite);
            int differenceRed = Math.abs(chipSetWaardes[1] - aantalRed);
            int differenceGreen = Math.abs(chipSetWaardes[2] - aantalGreen);
            int differenceBlue = Math.abs(chipSetWaardes[3] - aantalBlue);
            int differenceBlack = Math.abs(chipSetWaardes[4] - aantalBlack);
            int totalDifference = differenceWhite + differenceRed + differenceGreen + differenceBlue + differenceBlack;
            chipSetCombosDifferenceValues[teller - 1] = totalDifference;
            System.out.printf("\nCombo " + teller + ": " + Arrays.toString(cs.getChips()) + " = " + totalDifference);
            teller++;
        }
        newChipSet = chipSetCombos.get(smallestValueOfArrayIndex(chipSetCombosDifferenceValues));
        System.out.printf("\n\nThe least different ChipSet is: " + Arrays.toString(newChipSet.getChips()) + " ");
        return newChipSet;
    }

    private int smallestValueOfArrayIndex(int[] array) {
        int huidigeWaarde = array[0];
        int smallestIndex = 0;
        for (int j = 1; j < array.length; j++) {
            if (array[j] < huidigeWaarde) {
                huidigeWaarde = array[j];
                smallestIndex = j;
            }
        }
        return smallestIndex;
    }

    private int[] lowerBlack(int[] array) {
        return new int[]{array[0], array[1], array[2], array[3] + 2, array[4] - 1};
    }

    private int[] lowerBlue(int[] array) {
        return new int[]{array[0], array[1], array[2] + 2, array[3] - 1, array[4]};
    }

    private int[] lowerGreen(int[] array) {
        return new int[]{array[0] + 1, array[1] + 2, array[2] - 1, array[3], array[4]};
    }

    private int[] lowerRed(int[] array) {
        return new int[]{array[0] + 2, array[1] - 1, array[2], array[3], array[4]};
    }

    private int getTotalPoints(int[] array) {
        return ((array[0] * 1) + (array[1] * 2) + (array[2] * 5) + (array[3] * 10) + (array[4] * 20));
    }

    public String getName() {
        return this.name;
    }

    public int getPoints() {
        return this.points;
    }

    public ChipSet getChips() {
        return chips;
    }

}

芯片组.java

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;
    }

    public int[] getChips() {
        return this.chips;
    }
}

一些解释:

• 创建组合

We create some submethods the trade a chip in for it's lower chip. So for example black = 2 blues. Then we create 5 loops in order. The first ones checks if there are still black chips, if so reduce 1 black add 2 blues. Save this new combination in a list if the sum of the chips in the new ChipSet equals the original ChipSets value. Loop continues until there are no blacks anymore. Then it check if there are blues and repeats the same process until there are no reds anymore. Now we have list with all possible variations of X value in chips.

• 过滤器组合

You filter the ChipSets based on if you can pay X points with them without exchanging. We loop over all possible combinations of ChipSets created in the previous part. If you can pay with the ChipSet without exchanging add it to the filteredList of ChipSets. The result is a filered list with only valid ChipSets.

• 计算差异

For each ChipSet we count the number of chips of all colors in a ChipSet and substract the original chipset number of chips with it. You take the absolute value of that and make a sum of all those differences of the original and the combos colors. Now we have a number that represents the difference from the original. Now all we have to do is compare all the ChipSets ´difference number´. The one with the least difference we use to assign to the player.

简单吧