标签: coin-change

你好,我正在尝试创建一个algorythm,找出我可以改变回来的方式.但我只是不能正确实现,我一直得到4我应该得到6,我只是不明白为什么.

这是我在C#中的实现,它是从http://www.algorithmist.com/index.php/Coin_Change的伪代码创建的.

     private static int[] S = { 1, 2, 5 };
        private static void Main(string[] args)
        {
            int amount = 7;
            int ways = count2(amount, S.Length);
            Console.WriteLine("Ways to make change for " + amount + " kr: " + ways.ToString());
            Console.ReadLine();
        }    
static int count2(int n, int m)
        {
        int[,] table = new int[n,m];

        for (int i = 0; i < n; i++)
        {
            for(int j = 0; j < m; j++)
            {
                // Rules
                // …

我是prolog的新手，试图解决这个经典的硬币找零问题。

用公式M> = 0和M = P + 5 * N + 10 * D来更改（M，P，N，D）这是我的方法

change(M,P,N,D) :-
     M is P+5*N+10*D,
     P is M - (5*N+10*10).

几个测试用例

  change(100,10,8,5).
  True
  change(X,10,8,5).
  X = 100.

但是，如果我尝试

 change(100,P,8,5).

它给了我“参数没有被充分实例化”，而不是P = 10。

编辑：通过在谓词之间（0，M，P），之间（0，M，N），之间（0，M，D），之间的谓词来修复我的代码，M是P + 5 * N + 10 * D。

我是C#的新手,我有一个要解决的递归问题.我希望在这个硬币更换问题中获得最少数量的硬币.我已经为它调整了一个算法,但我需要返回一个类型为Change的对象,它将包含最小可能的组合.

我试图实现一个算法,但我有所有可能的组合.

using System;
using System.Collections.Generic;
using System.Linq;

// Do not modify change
class Change
{
    public long coin2 = 0;
    public long bill5 = 0;
    public long bill10 = 0;
}

class Solution
{

    // Do not modify method signature
    public static Change OptimalChange(long s)
    {
        Change _change = new Change();
        //To implement here
        return _change;
    }

    public static int GetCombinations(int total, int index, int[] list, List<int> cur)
    {
        if (total == 0)
        {
            foreach (var i in cur) …

我想知道硬币变化问题的算法的想法,其中每个面额具有infinte数量的硬币.意味着如何应用DP(如标准硬币更换问题)例如在套装1,10,15中,更改为35给出 - 2个硬币10和1个硬币15

还给我一个强制算法的想法.我知道迭代所有集合.但是如何在强制执行时改变每枚硬币的数量

我想找到换币的所有组合.1,2,5,10,20,50,100和200.(1分,2分..)如果硬币超过500(5欧元),它应该给-1.My代码与那些测试用例完美配合:numOfSplits 10 (11)numOfSplits 20(41)numOfSplits 100(4563).当我尝试使用numOfSplits 200或500的测试用例时,它会产生C堆栈溢出错误.我怎样才能使我的代码更好？

numOfSplits :: Integer -> Integer  
numOfSplits a  
    | (abs a) > 500 = -1  
    | (abs a) == 0 = 0  
    | otherwise = intzahler (makeChange [200,100,50,20,10,5,2,1] (abs a) 200)  

intzahler :: [[Integer]] -> Integer  
intzahler array  
    | array == [] = 0  
    | otherwise = 1 + intzahler (tail array)  

makeChange :: [Integer] -> Integer -> Integer -> [[Integer]]  
makeChange coins amount maxCoins  
    | amount < 0  = []  
    | amount == 0 …

我正在研究用Python 制作硬币问题的经典改造.这是我的实施.

def memo(fn):
    def helper(*args): # here, * indicate the fn take arbitrary number of argumetns
        d = {}
        if args in d:
            return d[args] # args is a tuple, immutable, hashable
        else:
            res = fn(*args) # here * expand a tuple as arguments
            d[args] = res
            return res
    return helper

@memo
def change(options, n):
    if n < 0 or options ==():
        return 0
    elif n == 0:
        return 1
    else:
        return change(options, n- options[0]) + change(options[1:], n) …

我一直在研究 Haskell 并且我成功地制作了一个算法来分解纸币中的给定货币价值，它需要对这个价值求和。可以在此处找到更好的解释（以及挑战本身）。

import Text.Printf
import Data.List
import Data.Ord

filterNearest :: Int->(Int->Bool)
filterNearest a = (\x -> (max a x) <= a)

findNearest :: Int->[Int]->Int
findNearest x possibilities = last $filter (filterNearest x) possibilities

decomposeOnce :: Int->[Int]->[Int]->[Int]
decomposeOnce x list possibilities = [findNearest x possibilities] ++ list

decomposeRecursive :: Int->[Int]->[Int]->[Int]
decomposeRecursive x list possibilities = if x /= 0
    then
        let decomposed = decomposeOnce x list possibilities
        in decomposeRecursive (x - decomposed!!0) decomposed possibilities
    else list

countGroup :: …

这是硬币兑换问题的一个版本。因此，这是一个动态规划问题。

我知道如何确定您是否可以找零，如果您最多可以使用每种面额的一枚硬币，或者您最多可以使用 k 枚硬币，但不能同时使用两者。

每次递归调用最小函数时,我的程序似乎都会崩溃.任何人都可以告诉我它崩溃的原因.在我调用最小函数后它会立即冻结.是因为即时通讯使用矢量吗？

#include <iostream>
#include <vector>
#include <math.h>
#include <algorithm>

using namespace std;

int minimum(vector<int> denom, int s, int N) //take in denomination , sizeofcoin, and value of N
{
    if(N == 0)
    {
        return 1;
    }
    else if(N < 0 || (N > 0 && s <=0))
    {
        return 0;
    }
    else
    {
        return min(minimum(denom,s - 1, N), 1 + minimum(denom, s,N-denom[s-1]));
    }
}
int main()
{
    int N;
    unsigned int sizeofcoin;
    cout << "Enter the value N to produce: …

嘿大家.我有个问题.我正在使用Visual Basic Express,我应该从事务中计算更改.

现在我会使用什么代码？我有一部分工作,但它开始有点混乱.

谢谢.

对于想要了解更多信息的人:

假设我有一美元,我去商店买东西.我必须要求用户输入他们花费的金额,然后计算更改并打印到屏幕上.

然后我应该使用最少数量的季度,硬币和硬币,并将其打印到屏幕上.

任何帮助将不胜感激.

我已经尝试为这个算法找到一个解决方案 3-4 天了，但似乎没有任何效果，而且可用的解决方案对我来说有点先进。它必须仅用条件来解决，因此不需要递归或动态编程。

我需要确定给定以下面额的找零所需的最少硬币数量：1、0.5、0.2、0.1、0.05、0.02 和 0.01。

输入如下：

商品的价格

客户支付的金额

目前的想法：

let price = +gets();
let paidSum = +gets();
//gets is used to accept number input
let change = paidSum - price;

我想我可以使用 Math.floor 来隔离整数部分并减去它，但随后我不知道如何处理剩余的总和。

模数是否可以测试剩余总和是否包含任何剩余的变化值，然后再次减去直到达到零？

我确实意识到这不是最好的问题，但我在这里不知所措，除此之外我还完成了所有其他任务。谢谢。

我正在寻找最有效的方法来计算购买金额的变化金额(季度,硬币,镍币和硬币).购买金额必须低于1美元,更改金额为1美元.我需要知道有多少人,硬币,镍币和便士才会回来.

设置字典是最好的吗？