Strategia / algoritmo per dividere il piatto in gettoni

Mi sembra che tu stia tentando di risolvere il Problema dello zaino se desideri una soluzione generale in cui qualsiasi denominazione lavoro.

Inserisci in questi termini questo è un problema di zaino senza limiti in cui tutti i valori sono -1 ei pesi sono la denominazione del chip.

Dovresti riuscire a trovare molte informazioni sul problema online.

In generale, poiché questa sembra una domanda a casa e non voglio dare la risposta, ecco la strategia per risolvere il problema.

• Trova la denominazione più grande pari o inferiore al valore del piatto e dividi il piatto con quella denominazione
• Ecco quanti di quella denominazione di chip di cui hai bisogno
• Prendi il resto del piatto e ripeti questi passaggi finché il piatto non è $ 0,00

Ad esempio

   17.5 / 10 = 1 with 7.5 remaining (we need one $10 chip)
    7.5 / 5  = 1 with 2.5 remaining (we need one  $5 chip)
   ...etc

... sembra che abbia ancora dato via la risposta.

In generale questo problema può essere indicato come problema di programmazione in numeri interi. Quindi il compito è

x_i = how many chip type i you have

maximize:

sum(-x_i)

subject to:

sum(chipvalue_i*x_i)=pot

x_i >= 0 and x_i is integer for all i

In generale questo tipo di problemi sono difficili da NP. Ma se la dimensione del piatto non è troppo grande, un algoritmo relativamente facile per il problema è il cosiddetto algoritmo branch-and-bound. Per la spiegazione dell'algoritmo, consultare: link , capitolo 9.5, pagina 289

O (n * c) algoritmo di programmazione dinamica in pseudocodice, dove n è la quantità di denaro in dollari (o centesimi, se ci sono valori di chip con una porzione di centesimi), e c è il numero di dimensioni dei chip. Restituisce 0 se non viene trovata alcuna formulazione del chip. Questo fornisce solo il conteggio dei chip. Per ottenere i conteggi dei chip effettivi, sostituire MoneyArray con una serie di Liste di chips e con un elenco di chipsize.

fun GetMinChipCount(Array ChipSizes, Int MoneyCount)
    MoneyArray = Int[1..MoneyCount]
    for i = 1 to MoneyCount:
        Int mincount = 0
        foreach Chip in ChipSizes:
            if Chip < i: continue
            if Chip = i: mincount = 1
            if Chip > i
                Int CountVal = MoneyArray[Chip-i]
                if CountVal = 0: continue;
                if mincount == 0 or mincount > CountVal + 1: mincount = CountVal + 1
        MoneyArray[i] = mincount;
    return MoneyArray[MoneyCount]

Quello che descrivi è meno un algoritmo "pot-to-chip" (nel poker reale, il vincitore si limita a raccogliere i gettoni dal centro del tavolo) e più un algoritmo di "colorazione" (una volta che un giocatore è pronto a partire , consegna la sua scorta al banchiere che riduce le fiches al numero minimo richiesto), che è fondamentalmente un algoritmo "che cambia" usando importi superiori a $ 1,00.

Ecco come scriverei in C #:

//I convert this enum to an array of its values, so you could skip this
public enum ChipDenom : int
{
   One = 1,
   Five = 5,
   Ten = 10,
   TwentyFive = 25,
   OneHundred = 100,
   FiveHundred = 500,
   OneThousand = 1000,
   FiveThousand = 5000,
   TenThousand = 10000
}

public Dictionary<ChipDenom, int> ColorUp(int chipAmount)
{
   int remainingAmount = chipAmount;

   //you could instead define an int[] containing the dollar values;
   var chipValues = Enum.GetValues()
                    .OfType<ChipDenom>()
                    .OrderByDescending(cd=>cd)
                    .ToArray();

   //If you do, the return value of this method should be Dictionary<int,int>
   var result = new Dictionary<ChipDenom, int>();

   while(remainingAmount > 0)
   {
      //find the largest chip denomination less than the remaining amount
      var highest = chipValues.First(cd=>(int)cd < remainingAmount);

      //determine how many of that chip can be used
      var quantity = remainingAmount / (int)highest;

      //and add it to the chip stack
      result.Add(highest, quantity);

      //and repeat with whatever's left over
      remainingAmount %= (int)highest;
   }

   return result;
}

...

//Usage:

var winnings = 13579;

//to determine the chips to give to a single player:
var chips = ColorUp(winnings);

foreach(var kvp in chips)
   Console.Writeline(String.Format("{0} : {1}", kvp.Key.ToString(), kvp.Value)

//to determine the chips to give to X players who split the pot:
var splitPlayers = 3;
var winnings = 13579;

var leftOver = winnings % splitPlayers;

var winningsPerPlayer = winnings / splitPlayers;

var playerChips = ColorUp(winningsPerPlayer);
var tableChips = ColorUp(leftOver);

Console.WriteLine("Each player receives:");

foreach(var kvp in playerChips)
   Console.Writeline(String.Format("{0} : {1}", kvp.Key.ToString(), kvp.Value);

Console.WriteLine("Leave in pot:");

foreach(var kvp in tableChips)
   Console.Writeline(String.Format("{0} : {1}", kvp.Key.ToString(), kvp.Value);

Un approccio a forza bruta consiste nel modificare l'algoritmo di base di @ Chad, ma poi, una volta trovata una soluzione, ricominciare da capo ma con un chip in meno nella pila della più grande denominazione rimasta. Quindi risciacquare e ripetere e buttare via che mai risultato è meno desiderabile. La condizione di fine è dove hai esaurito le denominazioni di chip, o sai che avrai sempre più chip.

Semplicemente cercando di rompere i chip a parte non tiene conto della divisibilità dei chip, non potrebbero avere alcun fattore comune (sebbene facciano nell'esempio sopra).

Quindi, supponendo che devi dividere $ 37 e hai alcune strane dimensioni dei chip:

$ 22, $ 10, $ 7, $ 1

Decrement 22's
22*1 + 10*1 + 7*0 + 1*5  = 37 with 7  chips

Decrement 10's
22*0 + 10*3 + 7*1 + 1*0  = 37 with 4  chips
22*0 + 10*2 + 7*2 + 1*3  = 37 with 7  chips
22*0 + 10*1 + 7*3 + 1*6  = 37 with 10 chips

Decrement 7's
22*0 + 10*0 + 7*5 + 1*2  = 37 with 7  chips
22*0 + 10*0 + 7*4 + 1*9  = 37 with 13 chips
22*0 + 10*0 + 7*3 + 1*16 = 37 with 19 chips
22*0 + 10*0 + 7*2 + 1*23 = 37 with 25 chips
22*0 + 10*0 + 7*1 + 1*30 = 37 with 31 chips
22*0 + 10*0 + 7*0 + 1*37 = 37 with 35 chips

Trova la risposta con aiuto Algoritmo dell'albero binario:

using System;

namespace MinimumStack
{
    public class Node
    {
        public static long[] denominations = { 1L, 5L, 10L, 25L, 50, 100L, 500L, 1000L, 5000L, 10000L, 25000L, 50000L, 100000L, 500000L, 1000000L, 5000000L, 10000000L, 250000000L, 500000000L, 100000000L, 500000000L, 1000000000L };
        public long Data { get; set; }

        public long Denom { get; set; }
        public long Denom1 { get; set; }
        public long Denom2 { get; set; }


        public int denomChip1 { get; set; }
        public int denomChip2 { get; set; }

        public long ChipCount { get; set; }
        public Node Left { get; set; }
        public Node Right { get; set; }
        public Node()
        {

        }
        public Node(long data,int index,long chipCount1)
        {
            this.Data = data;
            this.ChipCount = chipCount1;


            if(index > 0)
            {
                this.Denom = denominations[index+1];
                this.Denom1 = denominations[index];
                if(data >= denominations[index] && data >0)
                {
                    long chipcount1 = data / denominations[index];

                    long newdata = data - denominations[index] * chipcount1;
                    //if(newdata>0)
                    Left = new Node(newdata, index - 1, chipcount1); 
                } 
            }

            if( index-1 > 0)
            {
                this.Denom2 = denominations[index - 1]; 

                if(data>= denominations[index-1] && data > 0)
                {
                    long chipcount1 = data / denominations[index-1];
                    Console.WriteLine(data+ " data ======== " +denominations[index-1]+" = "+chipcount1);
                    long newdata = data - denominations[index-1] * chipcount1;
                    //if(newdata>0)
                    Right = new Node(newdata, index - 2, chipcount1); 
                } 
            } 

            if(index == 0)
            {

                //this.ChipCount = data;
                this.Denom = denominations[index+1];
                this.Denom1 = denominations[index];
                Left = new Node(0, index - 1, data); 
            }
            if(index-1 == 0)
            {

                //this.ChipCount = data;
                this.Denom2 = denominations[index-1];
                Right = new Node(0, index - 2, data); 
            } 

            //Console.WriteLine("===========================*************=====================================");

//            Console.WriteLine("===============================******************=================================");

        }

       /* 
        private void InsertRec(Node root, Node newNode)
        {
            if (root == null)
                root = newNode;

            if (newNode.Data < root.Data)
            {
                if (root.Left == null)
                    root.Left = newNode;
                else
                    InsertRec(root.Left, newNode);

            }
            else
            {
                if (root.Right == null)
                    root.Right = newNode;
                else
                    InsertRec(root.Right, newNode);
            }
        }
        */
    }
    public class Program
    {
        private Node _root;
        public static void Main(string[] args)
        {//Your code goes here
            Program p = new Program();
            long amount = 14;//15L;
            long[] str1 = { 1L, 5L, 10L, 25L, 50L, 100L, 500L, 1000L, 5000L, 10000L, 25000L, 50000L, 100000L, 500000L, 1000000L, 5000000L, 10000000L, 250000000L, 500000000L, 100000000L, 500000000L, 1000000000L };
            //Console.WriteLine("Hello, world!" + p.GetMaxDenomination(44440L));
            for (int j = str1.Length - 1; j >= 0; j--)
            {
                if (amount >= str1[j] && str1[j] > 1)
                {
                    Console.WriteLine((4/1)+"Hello, world! " +j);
                    p._root = new Node(amount, j, 0L);
                    break;
                }
            }
            p.DisplayTree();
            Console.WriteLine("Do something test "+ 44440L/10L);
            Console.WriteLine("================================================================");
           // p.DoSomething();
        }
        private void DisplayTree(Node root,long count)
        {
            if (root == null)
            {
               // Console.WriteLine("ChipCount "+count); 
                return;
            }
            //Console.WriteLine("Denom " +root.Denom +" ChipCount " +(root.ChipCount)); 
            if(root.Data == 0)
                Console.WriteLine("ChipCount "+(count)); 
          //  Console.WriteLine("================================================================");
            if (root.Left != null)
            DisplayTree(root.Left,root.Left.ChipCount+count);

           /* System.Console.WriteLine(root.Data + "Root "+root.Denom1+ " : "+root.Denom2+" chipcount "+root.ChipCount+ "Chip Denomination: "+root.Denom);

            if(root.Left != null)
                System.Console.WriteLine(root.Left.Data + " left " +root.Left.ChipCount);
            if (root.Right != null)
                System.Console.WriteLine(root.Right.Data + " right "+root.Right.ChipCount);
            */
            if (root.Right != null)
            DisplayTree(root.Right,root.Right.ChipCount+count);
         //  Console.WriteLine("================================================================");
        }
        public void DisplayTree()
        {
            DisplayTree(_root,_root.ChipCount);
        }
        public long GetMaxDenomination(long value)
        {
            long[] denominations = {1L,5L,10L,25L,50,100L, 500L, 1000L, 5000L, 10000L, 25000L, 50000L,100000L, 500000L, 1000000L, 5000000L, 10000000L,250000000L,500000000L, 100000000L, 500000000L, 1000000000L };
            long maxDenomination = denominations[0];
            for (int i = 1; i < denominations.Length; i++)
            {
                float val = value/denominations[i];
                Console.WriteLine("value "+ val);
                if (val > 0)
                {
                    maxDenomination = denominations[i];
                }
            }
            return maxDenomination;
        }

        public void DoSomething()
        {//{1L,5L,10L,25L,50,100L, 500L, 1000L, 5000L, 10000L, 25000L, 50000L,100000L, 500000L, 1000000L, 5000000L, 10000000L,250000000L,500000000L, 100000000L, 500000000L, 1000000000L };
            long[] str1 = {1L,5L,10L,25L,50,100L, 500L, 1000L, 5000L, 10000L, 25000L, 50000L,100000L, 500000L, 1000000L, 5000000L, 10000000L,250000000L,500000000L, 100000000L, 500000000L, 1000000000L };
            for(long i = 44440L;i<=44440L; i++)//1000000000L
            {
                // print("\(i)")
                //if(i%5 == 0)
                {
                    var amount = i;
                    var chipcount = 0L;
                    for( int j = str1.Length-1;j>=0;j--)//.reversed()
                    {// print(j)
                        if(amount/str1[j] > 0 && str1[j]>1)
                        {
                            //Console.WriteLine(str1[j]+" reach "+ amount +" here "+amount/str1[j] );
                            chipcount += amount/str1[j];
                            var k = amount/str1[j];
                            amount = amount - str1[j]*k;
                        }
                        else if(str1[j]==1)
                        {
                            Console.WriteLine(str1[j]+" reach "+ amount +" here "+amount );
                             chipcount+=amount;amount =0;
                        }
                        if(amount == 0)
                            break;
                    }
                    if(chipcount > 11)
                    {
                        Console.WriteLine(i+" amount will have chip "+ chipcount);
                        // print("\(i) amount will have chip \(chipcount)")
                    }
                }
            }
        }
    }
}