硬币更改贪婪算法

Question

Hy家伙，出于某种原因，我的贪婪硬币更改程序不起作用。该函数应返回最小数量的硬币，您可以更改一个值，并且还有一个数组，其中包括可用于此的硬币。我的程序没有显示任何内容，我不知道为什么。

public class Main { 

public static int coinChangeGreedy(int[] coins, int n) { 

     int result = 0; 

     while (n != 0) 
     { 

      for (int i=coins.length - 1 ; i>=0 ; i--) 
      { 
       if (coins[i] <= n) 
       { 
        n = n - coins[i]; 
        result++; 
       } 
      } 
     } 
     return result; 
    } 

    public static void main(String[] args) 
    { 
     int[] coins = {1, 2, 5}; 
     int n = 11; 

     coinChangeGreedy(coins, n); 

    } 

} 

Answer 1

那么，起初 - 你不打印任何东西 - 你只是运行该功能。
其次 - 你的代码中存在一些缺陷。你看 - 如果你发现一枚硬币可以工作，你就不应该去下一枚硬币，但是看看它是否“合适”。
以n=11为例。你有5作为第一个，然后移动到2.但你应该再次尝试5（防止for循环进入下一个元素）。看例子：

public static int coinChangeGreedy(int[] coins, int n) { 

     int result = 0; 

     while (n != 0) { 

      for (int i=coins.length - 1 ; i>=0 ; i--) { 
       if (coins[i] <= n) { 
        n = n - coins[i]; 
        System.out.println("Adding " +coins[i]); 
        i++; //neutralizing i-- with i++. 

        result++; 
       } 
      } 
     } 
     return result; 
    } 

不是你会看到5被采取两次。
P.s. - 如果你假设硬币阵列将会上升。 并打印出来，你只是去：

System.out.println("Total coins needed: " +coinChangeGreedy(coins, n)); 

此外 - 如果你想跟踪硬币的使用，你可以把它们每次选择的时间存储在一个ArrayList。 list.add（coins [i]）. And of course you declare and initialize that list`在开始。