问最小零钱或0-1背包

EN

根据我对你问题的理解，你似乎在争论你的问题是否可以用贪婪算法解决，或者它是否更像0-1背包问题，贪婪算法不会每次都给你最优解。

这里有一些关于贪婪算法和0-1背包问题的背景信息：

为了扩展贪婪算法，他们的工作基础是存在一些普遍最优的属性来选择下一项，并在局部工作。换句话说，对于贪婪的算法，它必须具有贪婪选择特性和最优子结构，这意味着贪婪算法做出的第一个选择可以选择在最优解中，并且最优解中包含较小的子问题的最优解。

另一方面，0-1背包问题不是一个可以贪婪地解决的问题。这在不显示贪婪选择属性的事实中最明显地被观察到。没有一个属性可以根据off来选择你的第一个和下一个项目；如果你选择最大的项目，可能是它恰好占据了太多的空间，没有更小的项目可以填满这个空间，而选择更小的项目会完全填满背包。如果您首先选择较小的项目，可能会导致您的背包现在有一个太小的空间，较大的项目填满，而更早选择这些较大的项目之一将完成背包。

0-1背包是一个需要dynamic programming解决方案的问题，它在非本地运行，用外行的话说，是一种优化的“蛮力”形式。换句话说，它可以被认为是对递归的优化。

您的问题是选择离散的项目来满足或接近最大长度限制。

对我来说，这听起来很像0-1背包问题，如果您想要任何数据集的最优解，则无法使用贪婪算法解决该问题。

相反，我们希望使用动态编程，并且可以看出，如果一个问题同时具有最优子结构和重叠子问题，则可以通过这种方式解决该问题。

0-1背包问题表现出最优子结构的原因是:从n个项目和W权重的数据集中可以获得的最大值是: n -1个项目和W权重的最大值，或者n-1个项目和项目n的W权重的最大值加上n的值。这些子问题的每个最优解可以组合在一起，为更大的问题创建最优解。

0-1背包问题也有重叠子问题，原因是:该问题的递归解决方案涉及尝试n项的所有组合，并检查这些项的权重是否小于W，然后找到这些值的最大值。这本质上涉及大量重复的工作，例如，尝试的每个项目组合可以计算出与以前在较少项目上计算的相同的总数，因此，使用简单的组合学，您可以看到时间复杂性变成了阶乘。

这就是为什么0-1背包问题和你的问题最好使用动态编程来解决，这样你就可以保存前一个子问题的答案，并参考你已经计算的总和来解决以后依赖于重叠子问题的答案的问题。

-

谢谢，祝你好运！