我遇到了关于更换自动售货机的问题（使用 10 克拉、20 克拉、50 克拉、100 克拉和 200 克拉硬币。）
假设咖啡售价 40 克拉。用户投入 2 欧元（标记为 200 克拉）。
现在我应该弄清楚如何将 160 克拉的零钱返还给用户。有 2 个条件：A) 采取最短的组合，但 B) 仅当收银机有足够的硬币来分发所述组合时。
所以在我的示例中，最短的组合是 100 克拉 + 50 克拉 + 10 克拉。但是，如果收银机中没有剩余 10 克拉硬币，则首选组合应该是 100 克拉 + 20 克拉 + 20 克拉 + 20 克拉。
public void coinChange (int change) {
int TwoEuroCount = 0, OneEuroCount= 0, FiftyCentsCount = 0, TwentyCentsCount = 0, TenCentsCount = 0;
while (change > 0) {
TwoEuroCount = change / 200;
if(register.availableTwoEuros(TwoEuroCount) == true) {
register.withdrawTwoEuros(TwoEuroCount);
change = change - 200 * TwoEuroCount;
//the method .availableTwoEuros returns true if AmountOfTwoEuros - TwoEuroCount >= 0
}
OneEuroCount = change / 100;
if(register.availableOneEuro(OneEuroCount) == true) {
register.withdrawOneEuro(OneEuroCount);
change = change - 100 * OneEuroCount;
}
FiftyCentsCount = change / 50;
if(register.availableFiftyCents(FiftyCentsCount) == true) {
register.withdrawFiftyCents(FiftyCentsCount);
change = change - 50 * FiftyCentsCount;
}
TwentyCentsCount = change / 20;
if (register.availableTwentyCents(TwentyCentsCount) == true) {
register.withdrawTwentyCents(TwentyCentsCount);
change = change - 20 * TwentyCentsCount;
}
TenCentsCount = change / 10;
if(register.availableTenCents(TenCentsCount) == true) {
register.withdrawTenCents(TenCentsCount);
change = change - 10 * TenCentsCount;
}
}
}
如果有足够的硬币，这非常适合找到最短的组合。但如果我从 AmountTenCents = 0 开始，该方法将只需要 1 欧元和 50 克拉，然后就这样了。
假设你有：
VALUESSUPPLY当前
VALUEWEIGHTSVALUES然后你可以找到一个组合的硬币，其总和为变化并且具有最小的总重量。
设组合
cc = [0, 1, 1, 2, 0]您从组合开始
c = [0, 0, 0, 0, 0]使用权重将隐含地向您保证最佳组合将具有最小权重，因此就是您正在寻找的结果。例如：
// Both combinations represent the change of 160 cents, but the
// first option has lower total weight and is the preferred
// choice as you only need 3 coins to return this change.
c = [1, 0, 1, 1, 0] => weight: 4*1 + 3*0 + 1*2 + 1*1 + 0*0 = 7
c = [0, 3, 0, 1, 0] => weight: 4*0 + 3*3 + 0*2 + 1*1 + 0*0 = 10
这样的东西应该有效：
import java.util.Arrays;
import java.util.stream.IntStream;
public class Change {
/** The number of unique coins. */
static final int N = 5;
static final int[] VALUES = { 10, 20, 50, 100, 200 };
static final int[] WEIGHTS = { 4, 3, 2, 1, 0 };
static final int[] SUPPLY = { 10, 35, 40, 100, 2 };
static int[][] result = {
{
// The minimum weight
Integer.MAX_VALUE
},
{
// The resulting combination of coins
0, 0, 0, 0, 0
}
};
public static void main(String[] args) {
int change = 160;
solve(new int[N], change);
if (result[0][0] == Integer.MAX_VALUE) {
System.out.println(
"Can't return the change with the given SUPPLY of coins"
);
} else {
System.out.println(Arrays.toString(result[1]));
}
}
static void solve(int[] c, int change) {
// check if out of supply
boolean isOutOfSupply = IntStream.range(0, N).anyMatch(i -> SUPPLY[i] < c[i]);
if (isOutOfSupply) return;
// compute weight
int weight = IntStream.range(0, N).map(i -> WEIGHTS[i] * c[i]).sum();
// compute sum
int sum = IntStream.range(0, N).map(i -> VALUES[i] * c[i]).sum();
if (sum == change && weight < result[0][0]) {
result[0][0] = weight;
result[1] = c;
} else if (sum < change) {
IntStream.range(0, N).forEach(i -> solve(increment(c, i), change));
}
}
static int[] increment(int[] array, int index) {
int[] clone = array.clone();
clone[index]++;
return clone;
}
}
在你的寄存器类中实现一个方法：
register.GetSmallestChangeAvailable()
这说明了可用的最小更改是什么。
在减去硬币之前检查一下。您还应该处理剩下一枚硬币但会使用两枚硬币的情况 - 例如，如果它有一枚 20 分的硬币并试图提供 40 分的零钱。 例如代替
if(register.availableFiftyCents(FiftyCentsCount) == true) {
register.withdrawFiftyCents(FiftyCentsCount);
change = change - 50 * FiftyCentsCount;
}
使用
for (int i = 0; i< fiftyCentCount; i++)
{
if ( (change - 50 == 0 || change - 50 >= register.GetSmallestChangeAvailable() && register.availableFiftCents(1))
{
register.withdrawFiftyCents(FiftyCentsCount);
change = change - 50 * FiftyCentsCount;
}
}
将重复的代码提取到单个方法中也会更好。
编辑： 如何实现 GetSmallestAvailableChange() 的选项取决于 Register 类的实现方式。但是，根据您在此处提到的内容，以下内容可行：
if (AvailableTenCents(1))
return 10;
if (AvailableTwentyCents(1))
return 20;
if (AvailableFiftyCents(1))
return 50;
等等..