用有限的硬币在C#中进行硬币找零 [英] Coin change in C# with limited coins
问题描述
我构建了下面的硬币找零(C#),它非常有效:
I built the following coin change (C#) that works perfectly:
class Program
{
static int amount = 0;
static void Main(string[] args)
{
EnterAmount();
int[] coins = new int[] { 500, 100, 50, 20, 10, 5, 2, 1 };
int Results = 0;
for (int i = 0; i < coins.Length; i++)
{
Results = amount / coins[i];
Console.WriteLine(Results + " x " + coins[i]);
amount -= Results * coins[i];
}
}
static void EnterAmount()
{
Console.Out.WriteLine("Enter an amount : ");
amount = int.Parse(Console.ReadLine());
}
}
我的问题是我不知道如何限制每个硬币的硬币数量。例如,我希望最多有4枚500欧元的硬币,6枚10欧元的硬币,5枚2欧元的硬币,等等。这真是太棒了,找零硬币会返回每个硬币使用的硬币数量。
My problem is that I don't know how to limit the quantity of coins for every coin. For exemple, I would like to have a maximum number of 4 coins of €500, 6 coins of €10, 5 coins of €2, etc. And it would be awesome that the coin change returns the number of coins used for every coin.
可以帮我吗?谢谢。
推荐答案
请注意,这段代码只是回答了有关限制谁的硬币数量的问题,但您的算法却不可行完整,因为您不需要考虑很多极端情况。
Be aware that this code just answers your question about who to limit your coins number, but your algorithm is not complete as you don't consider a lot of corner cases.
static void Main(string[] args)
{
var amount = 100000;
var availabeCoins = new CoinPack[]
{
new CoinPack { Value = 500, Amount = 2 },
new CoinPack { Value = 100, Amount = 3 },
new CoinPack { Value = 50, Amount = 5 },
new CoinPack { Value = 20, Amount = 1 },
new CoinPack { Value = 10, Amount = 2 },
new CoinPack { Value = 5, Amount = 0 },
new CoinPack { Value = 2, Amount = 10 },
new CoinPack { Value = 1, Amount = 500 }
};
var usedCoins = new CoinPack[]
{
new CoinPack { Value = 500 },
new CoinPack { Value = 100 },
new CoinPack { Value = 50 },
new CoinPack { Value = 20 },
new CoinPack { Value = 10 },
new CoinPack { Value = 5 },
new CoinPack { Value = 2 },
new CoinPack { Value = 1 }
};
for (int i = 0; i < availabeCoins.Length; i++)
{
usedCoins[i].Amount = amount / availabeCoins[i].Value;
if (usedCoins[i].Amount > availabeCoins[i].Amount)
{
usedCoins[i].Amount = availabeCoins[i].Amount;
}
amount -= usedCoins[i].Amount * usedCoins[i].Value;
}
foreach (var usedCoin in usedCoins)
{
Console.WriteLine(usedCoin.Value + " " + usedCoin.Amount);
}
}
class CoinPack
{
public int Value;
public int Amount;
}
UPD
效率低下,但我想它可以解决您的问题。您可以将其作为参考并自己进行改进。
UPD This solution is pretty inefficient, but I guess it solves your problem. You can take it as a reference and improve it yourself.
void Main(string[] args)
{
var amount = 6;
var availabeCoins = new List<CoinPack>
{
new CoinPack { Value = 500, Amount = 0 },
new CoinPack { Value = 100, Amount = 0 },
new CoinPack { Value = 50, Amount = 0 },
new CoinPack { Value = 20, Amount = 0 },
new CoinPack { Value = 10, Amount = 0 },
new CoinPack { Value = 5, Amount = 1 },
new CoinPack { Value = 2, Amount = 3 },
new CoinPack { Value = 1, Amount = 0 }
};
var usedCoins = new List<CoinPack>
{
new CoinPack { Value = 500, Amount = 0 },
new CoinPack { Value = 100, Amount = 0 },
new CoinPack { Value = 50, Amount = 0 },
new CoinPack { Value = 20, Amount = 0 },
new CoinPack { Value = 10, Amount = 0 },
new CoinPack { Value = 5, Amount = 0 },
new CoinPack { Value = 2, Amount = 0 },
new CoinPack { Value = 1, Amount = 0 }
};
if (Change(amount, availabeCoins, usedCoins) != null)
{
foreach (var usedCoin in usedCoins)
{
Console.WriteLine(usedCoin.Value + " " + usedCoin.Amount);
}
}
else
{
Console.WriteLine("Cannot find exact change");
}
}
List<CoinPack> Change(int amount, List<CoinPack> availableCoins, List<CoinPack> usedCoins)
{
if (amount == 0)
{
return availableCoins;
}
if (amount < 0)
{
return null;
}
foreach (var availableCoin in availableCoins.Where(ac => ac.Amount > 0 && amount >= ac.Value))
{
var newAvailableCoins = CopyCoins(availableCoins);
newAvailableCoins.First(c => c.Value == availableCoin.Value).Amount--;
var change = Change(amount - availableCoin.Value, newAvailableCoins, usedCoins);
if (change == newAvailableCoins)
{
usedCoins.First(c => c.Value == availableCoin.Value).Amount++;
return availableCoins;
}
}
return null;
}
List<CoinPack> CopyCoins(List<CoinPack> coinPacks)
{
var copy = new List<CoinPack>();
foreach (var coinPack in coinPacks)
{
copy.Add(new CoinPack { Value = coinPack.Value, Amount = coinPack.Amount });
}
return copy;
}
class CoinPack
{
public int Value;
public int Amount;
}
这篇关于用有限的硬币在C#中进行硬币找零的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!