证明或给出这个贪婪算法的反例
我在这个家庭作业问题上有困难。我认为主要的困惑来自于没有找到一个反例的基础。
设P1, . . . , Pn是存储在磁盘上的程序，程序Pi需要Si兆字节的存储空间，磁盘的容量为D兆字节，其中D小于兆字节存储空间之和
> (a)最大化磁盘上保存的程序数量。证明或给出一个反例:按照< code>Si递增的顺序选择程序的贪婪算法
（b） 尽可能多地使用磁盘的容量。证明或给出一个反例：贪婪算法，按照递减Si的顺序选择程序
编辑：抱歉没有澄清。
对于第(a)部分，我最初的尝试是假设它不会按照< code>Si递增的顺序选择程序。选择< code>Pa、< code>Pb和< code>Pc，其中< code>Sa
共有1个答案
a） 定理：按所需磁盘空间的递增顺序执行程序可确保尽可能多的程序运行。证明：证明是矛盾的。假设有其他选择程序的方法可以运行更多的程序。然后该方法必须在至少一种情况下选择不同的程序集；也就是说，它必须至少选择一个需要比未选择的程序更多空间的程序。然而，该方法还不如选择需要更少空间的程序，而不是将其与贪婪html" target="_blank">算法所做的选择区分开来的另一个程序。这与这种方法优于贪婪方法的假设相矛盾。因此，没有任何方法比贪婪方法更好：它是最优的。
b） 定理：按所需磁盘空间的降序处理程序并不能确保尽可能多地使用磁盘空间。证明：证明是举例。考虑大小为 10 的磁盘和需要磁盘空间 6、5 和 5 的程序的情况。按照所需磁盘空间的降序排列程序，我们只能使用 10 个可用存储单元中的 6 个，而我们可能采用两个程序，每个程序需要 5 个单元，总共 10 个单元。因此，贪婪方法并非在所有情况下都能给出最佳结果。
-
本文向大家介绍贪婪算法相关面试题，主要包含被问及贪婪算法时的应答技巧和注意事项，需要的朋友参考一下 参考回答： 贪婪算法(贪心算法)是指在对问题进行求解时，在每一步选择中都采取最好或者最优(即最有利)的选择，从而希望能够导致结果是最好或者最优的算法。贪婪算法所得到的结果往往不是最优的结果(有时候会是最优解)，但是都是相对近似(接近)最优解的结果。贪婪算法并没有固定的算法解决框架，算法的关键是贪婪策
-
有人有线索为什么它对案件2不起作用吗？非常感谢你的帮助。编辑：案例2的预期结果是6130美元。我好像得到了6090美元。
-
以下是我需要咨询以寻求帮助的问题： 编写一个贪婪算法，使用贪婪算法以尽可能少的硬币进行兑换。您将获得一个硬币值数组和一个金额：。返回一个包含每个硬币计数的数组。 例如：应该返回数组，该数组指示每枚硬币的数量：2枚50美分硬币，1枚25美分硬币，1枚10美分硬币），没有镍币（5美分），和2便士（1美分），加起来是137美分。 从computeChange返回的数组应该与第一个参数（硬币）的长度相同。
-
任务是典型的背包问题。求解时应采用贪婪算法。我设法创建了下面的代码，但它工作得太慢了。你能告诉我怎么加快速度吗？谢谢你。 c是背包的重量限制。n表示价格权重对的数量（这两个数字都是int类型，而不是float）。限制如下：（1）如果在相同重量的元素之间选择，价格最高的元素应该被取；（2）如果在相同价格和相同重量的元素之间选择，第一个输入的元素应该被取。
-
设计算法以实现给定问题的最佳解决方案。 在贪婪算法方法中，决策是从给定的解决方案域做出的。 由于贪婪，选择了似乎提供最佳解决方案的最接近的解决方案。 贪心算法试图找到一个本地化的最优解决方案，最终可能导致全局优化的解决方案。 但是，通常贪婪算法不提供全局优化的解决方案。 计数硬币 这个问题是通过选择最不可能的硬币来计算到期望的值，并且贪婪的方法迫使算法选择最大可能的硬币。 如果我们提供₹1,2,5
-
首先，是的，这是我的硬件，我觉得很难，所以我真的很感激一些指导。 我需要证明对于当