Найдите наименьшее количество монет, которое можно изменить, от 1 до 99 центов.

Question

Недавно я попросил моего коллегу написать алгоритм для решения этой проблемы:

Найдите наименьшее количество монет, которое можно изменить, от 1 до 99 центов. Монеты могут быть только пенни (1), никели (5), десять центов (10) и четверти (25), и вы должны иметь возможность делать каждое значение от 1 до 99 (с шагом в 1 цент), используя эти монеты.

Однако я понял, что на самом деле я не знаю, как сделать это сам, не изучая все возможные комбинации монет. Должен быть лучший способ решения этой проблемы, но я не знаю, как будет называться родовое имя для этого типа алгоритма, и я не могу придумать способ упростить его, помимо рассмотрения каждого решения.

Мне было интересно, сможет ли кто-нибудь указать мне правильное направление или предложить более эффективный алгоритм.

Answer 1

Вот простая версия на Python.

#!/usr/bin/env python

required = []
coins = [25, 10, 5, 1]

t = []
for i in range(1, 100):
    while sum(t) != i:
        for c in coins:
            if sum(t) + c <= i:
                t.append(c)
                break
    for c in coins:
        while t.count(c) > required.count(c):
            required.append(c)
    del t[:]

print required

При запуске выводит на стандартный вывод следующее.

[1, 1, 1, 1, 5, 10, 10, 25, 25, 25]

Код довольно понятен (спасибо Python!), Но в основном алгоритм состоит в том, чтобы добавить наибольшую доступную монету, которая не помещает вас выше текущей суммы, за которую вы стреляете, во временный список монет (t в этом случае). Как только вы найдете наиболее эффективный набор монет для определенной суммы, убедитесь, что в требуемом списке есть хотя бы столько монет. Сделайте это для каждой суммы от 1 до 99 центов, и все готово.

Answer 2

Вот мой дубль.Одна интересная вещь заключается в том, что нам нужно проверить минимальные монеты, необходимые для формирования до coin_with_max_value (25 в нашем случае) - только 1.После этого просто посчитайте сумму этих минимальных монет.С этого момента нам просто нужно добавить определенное количество coin_with_max_value, чтобы сформировать любое число вплоть до общей стоимости, в зависимости от разницы общей стоимости и найденной суммы.Вот и все.

Итак, для значений, которые мы берем, как только будут найдены минимальные монеты на 24: [1, 2, 2, 5, 10, 10].Нам просто нужно продолжать добавлять 25 монет для каждых 25 значений, превышающих 30 (сумма минимальных монет).Окончательный ответ на 99:[1, 2, 2, 5, 10, 10, 25, 25, 25]9

import itertools
import math


def ByCurrentCoins(val, coins):
  for i in range(1, len(coins) + 1):
    combinations = itertools.combinations(coins, i)
    for combination in combinations:
      if sum(combination) == val:
        return True

  return False

def ExtraCoin(val, all_coins, curr_coins):
  for c in all_coins:
    if ByCurrentCoins(val, curr_coins + [c]):
      return c

def main():
  cost = 99
  coins = sorted([1, 2, 5, 10, 25], reverse=True)
  max_coin = coins[0]

  curr_coins = []
  for c in range(1, min(max_coin, cost+1)):
    if ByCurrentCoins(c, curr_coins):
      continue

    extra_coin = ExtraCoin(c, coins, curr_coins)
    if not extra_coin:
      print -1
      return

    curr_coins.append(extra_coin)

  curr_sum = sum(curr_coins)
  if cost > curr_sum:
    extra_max_coins = int(math.ceil((cost - curr_sum)/float(max_coin)))
    curr_coins.extend([max_coin for _ in range(extra_max_coins)])

  print curr_coins
  print len(curr_coins)

Answer 3

Как я понял, если вы используете стандартные значения валютной системы, тогда очень просто подсчитать минимальное количество монет всего за один цикл. Просто всегда используйте максимальное значение монеты и, если это невозможно, проверьте следующий вариант. Но если у вас есть такая система, как у вас есть монеты, такие как 1,2,3,4, то она не работает. Я предполагаю, что вся идея иметь монеты 1,2,5,10,25 состоит в том, чтобы облегчить вычисления для людей.

Answer 4

Наткнулся сегодня на это, изучая https://www.coursera.org/course/bioinformatics

DPCHANGE(money, coins)
 MinNumCoins(0) ← 0
 for m ← 1 to money
        MinNumCoins(m) ← ∞
        for i ← 1 to |coins|
            if m ≥ coini
                if MinNumCoins(m - coini) + 1 < MinNumCoins(m)
                    MinNumCoins(m) ← MinNumCoins(m - coini) + 1
    output MinNumCoins(money)

Принимает доступную через запятую строку наименований и целевую сумму.

C # реализация:

    public static void DPCHANGE(int val, string denoms)
    {
        int[] idenoms = Array.ConvertAll(denoms.Split(','), int.Parse);
        Array.Sort(idenoms);
        int[] minNumCoins = new int[val + 1];

        minNumCoins[0] = 0;
        for (int m = 1; m <= val; m++)
        {
            minNumCoins[m] = Int32.MaxValue - 1;
            for (int i = 1; i <= idenoms.Count() - 1; i++)
            {
                if (m >= idenoms[i])
                {
                    if (minNumCoins[m - idenoms[i]] + 1 < minNumCoins[m])
                    {
                        minNumCoins[m] = minNumCoins[m - idenoms[i]] + 1;
                    }
                }
            }
        }
    }

Answer 5

Для этой проблемы жадный подход дает лучшее решение, чем DP или другие. Жадный подход: найдите наибольшую номинальную стоимость, которая меньше требуемой стоимости, и добавьте ее в набор монет для доставки. Уменьшите требуемые центы только что добавленным номиналом и повторяйте, пока требуемые центы не станут равными нулю.

Мое решение (жадный подход) в Java-решении:

public class MinimumCoinDenomination {

    private static final int[] coinsDenominations = {1, 5, 10, 25, 50, 100};

    public static Map<Integer, Integer> giveCoins(int requiredCents) {
        if(requiredCents <= 0) {
            return null;
        }
        Map<Integer, Integer> denominations = new HashMap<Integer, Integer>();

        int dollar = requiredCents/100;
        if(dollar>0) {
            denominations.put(100, dollar);
        }
        requiredCents = requiredCents - (dollar * 100);

        //int sum = 0;
        while(requiredCents > 0) {
            for(int i = 1; i<coinsDenominations.length; i++) {
                if(requiredCents < coinsDenominations[i]) {
                    //sum = sum +coinsDenominations[i-1];
                    if(denominations.containsKey(coinsDenominations[i-1])) {
                        int c = denominations.get(coinsDenominations[i-1]);
                        denominations.put(coinsDenominations[i-1], c+1);
                    } else {
                        denominations.put(coinsDenominations[i-1], 1);
                    }
                    requiredCents = requiredCents - coinsDenominations[i-1];
                    break;
                }
            }
        }
        return denominations;
    }

    public static void main(String[] args) {
        System.out.println(giveCoins(199));
    }

}

Answer 6

import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;

public class LeastNumofCoins 
{


    public int getNumofCoins(int amount)
        {
            int denominations[]={50,25,10,5,2,1};
            int numOfCoins=0;
            int index=0;
            while(amount>0)
            {
                int coin=denominations[index];
                 if(coin==amount)
                 {
                     numOfCoins++;
                     break;
                 }
                if(coin<=amount)
                    {
                        amount=amount-coin;
                        numOfCoins++;
                    }
                    else
                    {
                        index++;
                    }

            }
            return numOfCoins;
    }
    public static void main(String[] args) throws IOException 
    {

          Scanner scanner= new Scanner(new InputStreamReader(System.in));
          System.out.println("Enter the Amount:");
          int amoount=scanner.nextInt();
          System.out.println("Number of minimum coins required to make "+ amoount +" is "+new LeastNumofCoins().getNumofCoins(amoount));
          scanner.close();
    }
}

Answer 7

В общем, если у вас есть монеты COIN [] и ваш «диапазон изменения» 1..MAX, максимальное число монет должно быть найдено следующим образом.

Initialise array CHANGEVAL[MAX] to -1

For each element coin in COIN:
  set CHANGEVAL[coin] to 1
Until there are no more -1 in CHANGEVAL:
  For each index I over CHANGEVAL:
    if CHANGEVAL[I] != -1:
      let coincount = CHANGEVAL[I]
      For each element coin in COIN:
        let sum = coin + I
        if (COINS[sum]=-1) OR ((coincount+1)<COINS[sum]):
          COINS[sum]=coincount+1

Не знаю, еслипроверка на минимальность монет во внутреннем условном выражении, строго говоря, необходима.Я бы подумал, что минимальная цепочка дополнений к монетам окажется правильной, но лучше, чем потом сожалеть.

Answer 8

Есть несколько похожих ответов, но моё решение с Java кажется немного проще для понимания.Проверьте это.

public static int findMinimumNumberOfCoins(int inputCents) {

     // Error Check, If the input is 0 or lower, return 0.
     if(inputCents <= 0) return 0;

     // Create the List of Coins that We need to loop through. Start from highest to lowewst.
     // 25-10-5-1
     int[] mCoinsArray = getCoinsArray();

     // Number of Total Coins.
     int totalNumberOfCoins = 0;

     for(int i=0; i < mCoinsArray.length; i++) {

         // Get the Coin from Array.
         int coin = mCoinsArray[i];

         // If there is no inputCoin Left, simply break the for-loop
         if(inputCents == 0) break;

         // Check If we have a smaller input than our coin
         // If it's, we need to go the Next one in our Coins Array.
         // e.g, if we have 8, but the current index of array is 10, we need to go to 5.
         if(inputCents < coin) continue;

         int quotient = inputCents/coin;
         int remainder = inputCents%coin;

         // Add qutient to number of total coins.
         totalNumberOfCoins += quotient;

         // Update the input with Remainder.
         inputCents = remainder;
     }

     return totalNumberOfCoins;
 }

 // Create a Coins Array, from 25 to 1. Highest is first.
 public static int[] getCoinsArray() {

     int[] mCoinsArray = new int[4];
     mCoinsArray[0] = 25;
     mCoinsArray[1] = 10;
     mCoinsArray[2] = 5;
     mCoinsArray[3] = 1;

     return mCoinsArray;
 }

Answer 9

Вот простое решение c # с использованием Linq.

internal class Program
{
    public static IEnumerable<Coin> Coins = new List<Coin>
    {
        new Coin {Name = "Dime", Value = 10},
        new Coin {Name = "Penny", Value = 1},
        new Coin {Name = "Nickel", Value = 5},
        new Coin {Name = "Quarter", Value = 25}
    };
    private static void Main(string[] args)
    {
        PrintChange(34);
        Console.ReadKey();
    }
    public static void PrintChange(int amount)
    {
        decimal remaining = amount;
        //Order coins by value in descending order
        var coinsDescending = Coins.OrderByDescending(v => v.Value);
        foreach (var coin in coinsDescending)
        {
            //Continue to smaller coin when current is larger than remainder
            if (remaining < coin.Value) continue;
            // Get # of coins that fit in remaining amount
            var quotient = (int)(remaining / coin.Value);

            Console.WriteLine(new string('-',28));
            Console.WriteLine("{0,10}{1,15}", coin.Name, quotient);
            //Subtract fitting coins from remaining amount
            remaining -= quotient * coin.Value;
            if (remaining <= 0) break; //Exit when no remainder left
        }
        Console.WriteLine(new string('-', 28));
    }
    public class Coin
    {
        public string Name { get; set; }
        public int Value { get; set; }
    }
}    

Answer 10

Пример программы:

#include<stdio.h> 

    #define LEN 9 // array length
    int main(){
        int coins[LEN]={0,0,0,0,0,0,0,0,0}; // coin count
        int cointypes[LEN]={1000,500,100,50,20,10,5,2,1}; // declare your coins and note here {ASC order}   
        int sum =0; //temp variable for sum
        int inc=0; // for loop
        int amount=0; // for total amount
        printf("Enter Amount :");
        scanf("%d",&amount);
        while(sum<amount){
            if((sum+cointypes[inc])<=amount){
                   sum = sum+  cointypes[inc];
                    //printf("%d[1] - %d\n",cointypes[inc],sum);
                    //switch case to count number of notes and coin
                   switch(cointypes[inc]){
                    case 1000:
                           coins[0]++;
                           break;
                    case 500:
                           coins[1]++;
                           break;
                    case 100:
                           coins[2]++;
                           break;
                    case 50:
                           coins[3]++;
                           break;               
                    case 20:
                           coins[4]++; 
                           break;
                    case 10:
                           coins[5]++;
                           break;
                    case 5:
                           coins[6]++;
                           break;
                    case 2:
                           coins[7]++;
                           break;
                    case 1:
                           coins[8]++;
                           break;
                       }
                }else{
                   inc++;
                }
            }
        printf("note for %d in\n note 1000 * %d\n note 500 * %d\n note 100 * %d\n note 50 * %d\n note 20 * %d\n note 10 * %d\n coin 5 * %d\n coin 2 * %d\n coin 1 * %d\n",amount,coins[0],coins[1],coins[2],coins[3],coins[4],coins[5],coins[6],coins[7],coins[8]); 

    }