java - 找零所需的最大硬币数量

Question

我正在尝试做这个问题，给定一定面额的硬币，我想找到最大数量的硬币来找零。

例子 比如说，我得到了值(value) 3 和 5 的硬币，我想找零 15，解决方案是 {3,3,3,3,3}(感谢 JoSSte 指出) 同样，假设给定值(value) 3 和 5 的硬币，我想找零 7，我需要显示“没有可能的解决方案”

我能够按照以下方式找到最小数量的硬币

import java.util.ArrayList;
import java.util.Arrays;


public class Minimum
{
    static int[] options = {5,3};

    public static void main(String[] args)
    {
        ArrayList<Integer> result = new ArrayList<Integer>();

        result = fun(15);
        if(result.size() == 999)
             System.out.println("Not possible to make change with this denomination");
        else 
        {
            for(int i = 0;i<result.size();i++)
                System.out.print(result.get(i));
        }
    }

    static ArrayList<Integer> fun(int n)
    {       
        if(n == 0)
        {
            ArrayList<Integer> totalret = new ArrayList<Integer>();
            return totalret;
        }

        if(n < 0)   
        {
            ArrayList<Integer> totalret  = new ArrayList<Integer>(Arrays.asList(new Integer[999]));
            return totalret;
        }

        ArrayList<Integer> totalret  = new ArrayList<Integer>(Arrays.asList(new Integer[999]));
        for(int i = 0;i<options.length;i++)
        {
            ArrayList<Integer> reci = fun(n-options[i]);

            ArrayList<Integer> reti = new ArrayList<Integer>();
            reti.addAll(reci);
            reti.add(options[i]);

            if(reti.size() < totalret.size())
                totalret = reti;
        }
        return totalret;
    }
}

请注意，我有一个名为 if(n<0) 的检查，通过将它们的大小设置为一个非常大的数字(不能是最小值)，将不加起来等于总和的组合从选项中删除。

但是，我如何修改上面的代码才能找到最大硬币数

Answer 1

对于您的解决方案，您必须检查 n=1,2 的条件。如果 n=1,2 你可以返回 ans 作为 999。

你的函数必须如下所示

 static ArrayList<Integer> fun(int n)
   {       
     if(n == 0)
     {
            ArrayList<Integer> totalret = new ArrayList<Integer>();
            return totalret;
        }

        if(n < 0 || n==1 || n==2)   
        {
            ArrayList<Integer> totalret  = new ArrayList<Integer>(Arrays.asList(new Integer[999]));
            return totalret;
        }

        ArrayList<Integer> totalret  = new ArrayList<Integer>(Arrays.asList(new Integer[999]));
        for(int i = 0;i<options.length;i++)
        {
            ArrayList<Integer> reci = fun(n-options[i]);

            ArrayList<Integer> reti = new ArrayList<Integer>();
            reti.addAll(reci);
            reti.add(options[i]);

            if(reti.size() < totalret.size())
                totalret = reti;
        }
        return totalret;
    }

希望这能奏效..