java - 硬币兑换算法

我正在玩扑克游戏。在我的应用程序中，我有一个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(5 + 5 + 10 = 20)的[0,0,2,1,0]，并且我想用自己的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]。

我希望我的问题很清楚，如果不是，请发表评论，我将作进一步解释。

最佳答案

，这是一个编辑，我完全重新设计了答案。

**从游戏角度看问题**
玩家有2个绿色筹码(5分)和1个蓝色(10分)。总计20分。现在，玩家想购买价格为16点的游戏内图标。玩家有足够的钱购买物品。因此，玩家支付16点，但是他会给商店多少点才能正确支付。

现在，我已经编写了一个工作示例，其中包含所有已完成的工作。

代码

程式库

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.");
        }

    }
}

播放器

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

}

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

一些解释:

创建组合

过滤器组合

计算差异

简单吧

关于java - 硬币兑换算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/27652022/