最少硬币零钱或0-1背包

Question

我有这样的数据集：

长度：233333450560650780限制：5400

现在我的问题是，从设定的最高长度到最低长度中选择项目，以弥补限制或尽可能接近。

我知道背包和最小硬币兑换都能解决我的问题。我想知道哪个更好。

请注意，硬币变化是使用贪婪算法，背包使用动态编程

Answer 1

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

以下是关于贪婪算法和0-1背包问题的一些背景信息：

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

另一方面，0-1背包问题不是一个可以贪婪解决的问题。最明显的是，贪婪选择属性没有显示。没有一个属性可以根据off选择你的第一个和下一个物品；如果你选择最大的物品，可能是它碰巧占用了太多的空间，没有更小的物品可以填满这个空间，而选择更小的物品会完全填满背包。如果您先选择较小的物品，可能会导致您的背包现在的空间太小，无法容纳较大的物品，而早些时候选择其中一个较大的物品将完成背包。

0-1背包是一个需要动态规划解决方案的问题，它以非局部方式运行，用外行的话说，是一种优化的“蛮力”。换句话说，它可以被认为是对递归的优化。

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

这听起来像是对我来说，几乎完全像0-1背包问题，如果你想要任何数据集的最优解决方案，就不能用贪婪算法来解决。

相反，我们想要使用动态规划，你可以看出，如果一个问题同时有最优子结构和重叠子问题，那么它可以通过这种方式解决。

0-1背包问题显示了最优子结构，因为：从n个项目和W个重量的数据集可以获得的最大值是：n-1个项目和W个重量的最大值，或者n-1个项目和W个重量的最大值，加上n的值。每个子问题的最优解可以组合起来，为更大的问题创建最优解。

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

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

-

谢谢，祝你好运！