证明或给出这个贪心算法的反例
Prove or give a counter example for this greedy algorithm
我在做这道作业题时遇到了问题。我认为主要的困惑来自于没有确定反例的基础。
Let P1, . . . , Pn be programs stored on a disk. Program Pi requires
Si megabytes of storage, and the capacity of the disk is D
megabytes. Where D is less than the sum of megabytes of storage
(a) maximize the number of programs held on the disk. Prove or give a counter-example: greedy algorithm that selects programs in order of
increasing Si
(b) use as much of the capacity of the disk as possible. Prove or give a counter-example: greedy algorithm that selects programs in
order of decreasing Si
编辑：
很抱歉没有澄清。
对于 (a) 部分，我最初的尝试是假设它不会 select 按 Si 递增的顺序进行编程。选择 Pa、Pb 和 Pc，其中 Sa<=Sb<=Sc，此后我真的不明白如何走得更远，第 (b) 部分问了同样的问题，但减少了 Si.
a) 定理：以磁盘 space 的递增顺序获取程序需要确保尽可能多的程序 运行 。证明：证明是反证法。假设有一些其他选择程序的方法允许更多 运行。那么这个方法必须 select 至少在一种情况下是一组不同的程序；也就是说，它必须 select 至少有一个程序比一个未 select 需要更多 space 的程序。但是，该方法还不如 selected 需要更少 space 的程序，而不是另一个将它与贪婪算法制作的 selection 区分开来的程序。这与该方法优于贪心方法的假设相矛盾。因此，没有比贪心法更好的方法了：它是最优的。
b) 定理：按所需磁盘 space 的降序排列程序并不能确保尽可能多地使用磁盘 space。证明：证明是通过例子。考虑大小为 10 的磁盘和需要磁盘 space 6、5 和 5 的程序的情况。按所需磁盘 space 的降序排列程序允许我们仅使用 10 个可用存储单元中的 6 个，而我们可能已经采取了两个程序，每个程序需要 5 个单元，总共 10 个单元。因此，贪心法并不能在所有情况下给出最优结果。
我在做这道作业题时遇到了问题。我认为主要的困惑来自于没有确定反例的基础。
Let
P1, . . . ,Pnbe programs stored on a disk. ProgramPirequiresSimegabytes of storage, and the capacity of the disk isDmegabytes. WhereDis less than the sum of megabytes of storage
(a) maximize the number of programs held on the disk. Prove or give a counter-example: greedy algorithm that selects programs in order of increasing
Si(b) use as much of the capacity of the disk as possible. Prove or give a counter-example: greedy algorithm that selects programs in order of decreasing
Si
编辑： 很抱歉没有澄清。
对于 (a) 部分，我最初的尝试是假设它不会 select 按 Si 递增的顺序进行编程。选择 Pa、Pb 和 Pc，其中 Sa<=Sb<=Sc，此后我真的不明白如何走得更远，第 (b) 部分问了同样的问题，但减少了 Si.
a) 定理：以磁盘 space 的递增顺序获取程序需要确保尽可能多的程序 运行 。证明：证明是反证法。假设有一些其他选择程序的方法允许更多 运行。那么这个方法必须 select 至少在一种情况下是一组不同的程序；也就是说，它必须 select 至少有一个程序比一个未 select 需要更多 space 的程序。但是，该方法还不如 selected 需要更少 space 的程序，而不是另一个将它与贪婪算法制作的 selection 区分开来的程序。这与该方法优于贪心方法的假设相矛盾。因此，没有比贪心法更好的方法了：它是最优的。
b) 定理：按所需磁盘 space 的降序排列程序并不能确保尽可能多地使用磁盘 space。证明：证明是通过例子。考虑大小为 10 的磁盘和需要磁盘 space 6、5 和 5 的程序的情况。按所需磁盘 space 的降序排列程序允许我们仅使用 10 个可用存储单元中的 6 个，而我们可能已经采取了两个程序，每个程序需要 5 个单元，总共 10 个单元。因此，贪心法并不能在所有情况下给出最优结果。