Случайно распределить банкноты разных значений, чтобы соответствовать общей стоимости

Question

Учитывая массив банкнот со значениями = [1, 5, 10, 20, 50, 100], каков наилучший метод их случайного распределения, чтобы соответствовать общей сумме, например, 363? Я не хочу использовать модуль и добавить найти остаток, добавив сначала большие заметки. Я бы хотел, чтобы оно было более случайным, чтобы оно могло иметь более естественное распределение, в котором банкноты составляют сумму.

В настоящее время я делаю это:

int temp = totalAmount;
for (int i = 0; i < values.Length; i++)
{
   amounts[i] = temp / values[i];
   temp %= values[i];
}

Это будет дайте мне распределение нот 3x100, 1x50, 1x10, 3x1, но я бы предпочел, чтобы это было что-то вроде 1x100, 3x50, 2x20, 6x10, 13x13, хотя я не могу придумать хорошую стратегию.

Answer 1

Главным образом для испытания и чтобы увидеть, как это происходит, я написал небольшой класс для вычисления всех возможных комбинаций, затем вы можете взять из этого ведра.
В качестве бонуса, это позволит получить любое количество уникальных комбинации из списка (с удалением).
Однако я встроил ограничение для каждого типа заметки, например. 20x. Без каких-либо ограничений это будет работать очень долго (или, возможно, не хватит памяти).

public static void Main()
{
    var C = new Combinations();
    int targetValue = 363;
    int limitPerNote = 20;

    foreach(int v in new[] {1, 5, 10, 20, 50, 100})
    {
        int maxCnt = (int)(targetValue / v);
        maxCnt = Math.Min(maxCnt, limitPerNote);
        C.Add(v, maxCnt);
    }

    List<String> Results = new List<String>();
    while(!C.Inc())
    {
        if(C.TotalValue==targetValue)
        {
            //Console.WriteLine(C.CurrentCombinationToString());
            Results.Add(C.CurrentCombinationToString());
        }
    }
    Console.WriteLine($"{Results.Count} combinations found");

    Random random = new Random();
    Console.WriteLine($"Random combination:");
    Console.WriteLine(Results[random.Next(0, Results.Count)]);
}

public class Combinations
{
    private List<CombinationItem> Items {get; set;} = new List<CombinationItem>();

    public void Add(int value, int maxCount)
    {
        Items.Add(new CombinationItem() {Value=value, MaxCount = maxCount});
    }

    public bool Inc()
    {
        int i = Items.Count -1;
        bool overflowFlag = true;
        while(overflowFlag)
        {
            overflowFlag = Items[i].Inc();
            if(overflowFlag) i--;
            if(i<0) return true; // final overflow, last combination reached
        }
        return false; // return without final overflow
    }

    public int TotalValue
    {get{ return Items.Sum((item) => item.Value * item.Count); }}

    public string CurrentCombinationToString()
    {
        return String.Join(" + ", Items.
        Where((item) => item.Count >0).
        Select((item) => $@"{item.Count}x {item.Value}"));
    }

}

public class CombinationItem
{
    public int Value {get; set;}
    public int Count {get; set;}
    public int MaxCount {get; set;}

    public bool Inc()
    {
        // returns true on overflow
        Count++;
        if(Count > MaxCount)
        {
            Count=0;
            return true;
        }
        else
            return false;
    }
}

Answer 2

Если вы действительно хотите, чтобы это было случайно, вы можете сделать что-то вроде этого:

var rnd = new Random();
int currentValue = 0;
var selectedNotes = new List<int>();

int[] notes = {1, 5, 10, 20, 50, 100};
int targetValue = 363;

while (currentValue < targetValue)
{
    int v = rnd.Next(0, notes.Length);

    if (currentValue + notes[v] > targetValue)
    {
        continue;
    }

    selectedNotes.Add(notes[v]);
    currentValue += notes[v];
}

foreach (var note in selectedNotes.GroupBy(z => z).Select(z => new {BankNote = z.Key, Quantity = z.Count()})
    .OrderByDescending(z => z.BankNote))
{
    Console.WriteLine($"{note.Quantity}x{note.BankNote}");
}

Answer 3

Это будет работать для вас:

        Random random = new Random();

        int[] values = { 1, 5, 10, 20, 50, 100 };
        int[] amounts = new int[values.Length];
        int totalAmount = 363;

        int left = totalAmount;
        while (left > 0)
        {
            int nextNote = random.Next(0, values.Length);
            if (values[nextNote] < left)
            {
                left -= values[nextNote];
                amounts[nextNote]++;
            }
        }