我有这样的数据集：
长度：233，333，450，560，650，780限制：5400
现在，我的问题是从长度设置为最高到最低的长度中选择一个项目，以弥补限制或尽可能接近。
我知道背包和零钱都可以解决我的问题。我想知道哪一个更可取。
请注意，硬币找零使用贪婪算法，背包使用动态编程
根据我对您问题的理解，您似乎正在辩论是否可以使用贪婪算法解决问题，或者更像是0-1背包问题，而贪婪算法无法为您提供最佳解决方案每次。
以下是有关贪心算法和0-1背包问题的一些背景信息：
为了扩展贪婪算法，它们的工作是基于一些普遍最优的属性，以便从中选择下一个项目并在本地工作。换句话说，对于一个贪婪的算法，它必须具有贪婪选择属性和最优子结构，这意味着贪婪算法can做出的第一选择应在最优解决方案中进行选择，并且最优解包含其中较小子问题的最优解。
另一方面，0-1背包问题不是可以贪婪地解决的问题。在显示not贪婪选择属性这一事实中，最明显地观察到了这一点。没有一个属性可以基于off选择您的第一个和下一个项目；如果您选择最大的物品，则可能是因为它占用了太多的空间，并且没有较小的物品可以填充该空间，而选择较小的物品可能会完全充满背包。如果您首先选择较小的物品，则可能导致背包的空间现在太小而无法装满较大的物品，并且较早选择其中一个较大的物品将完成背包。
0-1背包是一个需要动态编程解决方案的问题，该解决方案是非本地操作的，并且是通俗易懂的术语，是一种优化的“蛮力”形式。换句话说，可以将其视为对递归的优化。
您的问题是选择离散的项目来满足或接近最大长度限制。
在我看来，这几乎与0-1背包问题完全相同，如果您想对任何数据集寻求最佳解决方案，都无法用贪婪算法解决。
相反，我们要使用动态编程，并且可以说，如果问题同时具有最优子结构和重叠子问题，则可以通过这种方式解决。
0-1背包问题显示最佳子结构，原因是：从n项和W权重的数据集中可以获得的最大值是：n-1项和W权重的最大值，或者，n-1项和W-项n权重的最大值，加上n的值。这些子问题的最优解中的每一个都可以组合起来，为更大的问题创建最优解。
0-1背包问题也具有重叠子问题，原因如下：该问题的递归解决方案包括尝试n个项目的所有组合，并检查这些项目的权重是否小于W，然后找到那些值的最大值。这固有地涉及许多重复性工作，因此所尝试的每种项目组合都可以计算出与以前针对较少的项目计算出的总数相同的总数，因此，使用简单的组合运算法则，您可以看到时间复杂度成为因数。
这就是为什么0-1背包问题和您的问题可以使用动态编程来最好地解决的原因，因此您可以保存先前子问题的答案，并参考已经计算出的总和来解决依赖于重叠子问题的以后问题”答案。
谢谢，祝你好运！