貪婪算法

Question

我是算法新手，目前正在學習使用you-tube視頻教程/講座和一本書，我首先觀看視頻，然後閱讀本書，最後從本書中嘗試一個問題，以確保我已經學會了正確的話題。我目前使用貪婪算法，這是非常令人困惑的。

書中有各種問題，但我無法理解和回答一個特定的問題。

首先它給出的問題是（我剛剛複製文本）。

有一組大小爲{x1; x2; ..... xn}和容量爲B的容器B.所有這些都是正整數。嘗試找到這些對象的子集 ，以使它們的總大小小於或等於B，但儘可能接近B.

所有對象都是一維的。例如，如果對象的大小爲4,7,10,12,15和 B = 20，那麼我們應該選擇總大小爲19（或等同於7和12）的4和15。 對於以下每個貪婪算法，通過創建 反例來證明它們不是最優的。儘量讓你的例子儘可能地糟糕，其中「壞」 是衡量的最佳和貪婪的解決方案之間的比例。因此，如果最好的 解決方案的值爲10，而貪婪解決方案的值爲5，則比率爲2.

如何爲以下內容執行此操作？

1）始終選擇尺寸最大的物體，以使其他所有已選對象的總尺寸不超過B.對其餘物體重複此操作。

Answer 1

假設的問題以下實例：

你有大小2n的盒子，大小n+1的一個元素，其餘都是規模n的。

很容易看出最優的是尺寸爲n的2個元素，而貪婪會得到一個大小爲n+1的元素。

由於它對每個n都是如此，它實際上給你一個期望的比率，至少使用這個貪婪的方法2。

Answer 2

這聽起來類似於0-1揹包問題，其中每個項目具有不同的大小，但具有相同的值，這意味着任何一個項目都沒有任何偏好被放入除了其大小之外的箱子。在您的代碼中，您需要檢查每個項目並計算最大總大小，以便在不超過容器容量的情況下將其放入容器中。