我需要使用裝箱算法還是揹包？

Question

這裏的問題陳述：

我米巧克力棒，整數的長度，並且ñ孩子誰 想要的巧克力整數金額。如果巧克力總需求量爲 ，那麼孩子的總巧克力數量少於或等於巧克力總數 。您需要編寫一個算法，將巧克力分配給 ，方法是對酒吧進行最少次數的切割。

例如，對於中號 = {1,3,7}，Ñ = {1,3,4}，切口的至少數將是1。

我不沒有任何正式的算法經驗，任何人都可以給我任何提示，我應該開始閱讀，以有效的方式解決這個問題？

Answer 1

這個任務可以簡化爲解決幾個揹包問題。爲了解決這些問題，通常使用貪婪搜索的原則，剪切次數是搜索的標準。

該算法的第一個顯而易見的步驟是檢查天平。 第二步是安排條形和巧克力需求的陣列，這將簡化進一步的計算。這實現了貪婪搜索的原則。 第三個明顯的步驟是找到並使用所有條形，其大小與需求一致。

下一步是找到並使用滿足需求的酒吧的所有組合。該任務需要按照需求的降序進行「貪婪」搜索，並在進一步的計算中繼續進行。這個標準並不是最佳的，但它可以形成一個基本的解決方案。

如果不是所有的孩子都收到巧克力，那麼切口就變得很明顯。搜索應根據瓷磚的下降尺寸進行。首先，應該檢查所有的可能性，一次給兩個孩子切割瓷磚，然後相同，但如果使用一個現有瓷磚等等。 之後，有一個明顯的變體「一切 - 一個需要」，允許以形成基礎變體。但是如果仍有計算資源，則可以首先使用它們來計算「兩個切口 - 三個需求」類型的選項等。

進一步優化包括返回到以下變體的步驟和計算。