为什么我们应该使用带记忆的动态编程来解决-最小硬币数量来进行更改

Question

问题陈述：给定无限供应值为 {C1， C2， ...， Cn} 的硬币和一个总和，找到可以表示总和 X 的最小硬币数。

网络上的大多数解决方案都包括带有记忆的动态编程。以下是来自Youtube的一个例子：https://www.youtube.com/watch?v=Kf_M7RdHr1M

我的问题是:为什么我们不先对硬币数组进行降序排序，然后通过最小化总和直到达到0来开始递归探索？当我们达到0时，我们知道我们已经找到了需要的硬币来补足总数。因为我们按降序对数组进行了排序，所以我们知道我们总是会选择最大的硬币。因此，当总和第一次下降到0时，计数必须是最小的。

如果您帮助了解我的算法的复杂性并将其与具有记忆方法的动态编程进行比较，我将不胜感激。

对于simplicty，我们假设总会有一个“1美元”硬币，因此总会有一种方法来凑成这个总数。

import java.util.*;

public class Solution{
    public static void main(String [] args){
        MinCount cnt=new MinCount(new Integer []{1,2,7,9});
        System.out.println(cnt.count(12));
    }
}

class MinCount{
     Integer[] coins;

     public MinCount(Integer [] coins){
        Arrays.sort(coins,Collections.reverseOrder());
        this.coins=coins;
    }

     public int count(int sum){
        if(sum<0)return Integer.MAX_VALUE;
        if(sum==0)return 0;     
        int min=Integer.MAX_VALUE;
        for(int i=0; i<coins.length; i++){
            int val=count(sum-coins[i]);    
            if(val<min)min=val;
            if(val!=Integer.MAX_VALUE)break;
        }
        return min+1;
     }
}

Answer 1

#recursive solution in python
import sys
class Solution:
    def __init__(self):
        self.ans=0
        self.maxint=sys.maxsize-1
    def minCoins(self, coins, m, v):
        res=self.solve(coins,m,v)
        if res==sys.maxsize-1:
            return -1
        return res
        
    def solve(self,coins,m,v):
        if m==0 and v>0:
            return self.maxint
        if v==0:
            return 0
        
        if coins[m-1]<=v:
            self.ans=min(self.solve(coins,m,v-coins[m-1])+1,self.solve(coins,m-1,v))
            return self.ans
        else:
            self.ans=self.solve(coins,m-1,v)
            return self.ans

Answer 2

我将用一些算法设计建议来补充已经提供给你的问题的答案。

您提出的解决方案是所谓的“贪婪算法”：一种问题解决策略，它在每个阶段做出局部最优选择，并希望找到全局最优。

在许多问题中，贪婪策略不会产生最优解。证明算法正确性的最佳方法是找到一个反例，例如“52美元”、“50美元”和“1美元”硬币的情况。为了找到反例，史蒂文·斯基纳在《算法设计手册》一书中给出了以下建议：

• 小处着眼：当一个算法失败时，通常有一个非常简单的例子来说明它失败了。
• 寻找弱点：如果提出的算法是“总是采取最大的”（即贪婪的算法）的形式，想想为什么这可能是错误的做法。特别。。。
• 打个平局：打破贪婪算法的一种狡猾方法是提供所有大小相同的实例。这样，算法可能没有什么可以作为其决策的基础。
• 寻求极端：许多反例是巨大和微小，左和右，少和多，近和远的混合体。验证或推理极端的例子通常比更混乱的例子更容易。

Answer 3

假设你有价值1美元、50美元和52美元的硬币，你的总数是100美元。你提出的算法将产生一个使用49个硬币的解决方案（52美元1美元…1美元1）；但是正确的最小结果只需要2个硬币（$50$50）。

（顺便说一句，我认为写作是作弊

简单地说，我们假设总是有一枚“1美元”硬币，因此总有办法弥补这个数字。

当这不在问题陈述中时，因此在其他来源中不假设。这有点像问“为什么排序算法总是花很多精力来重新排列元素，而不仅仅是假设元素一开始的顺序是正确的？但碰巧的是，即使假设存在1美元的硬币也不能保证天真/贪婪的算法会找到最佳解决方案。