總和小於N的最少子集

Question

我有一個特定的子問題，因此我無法提出最佳解決方案。這個問題類似於問題的子集總數組以及空間填充問題，但我沒有看到任何地方提出的具體問題。我不一定需要最佳解決方案（因爲我相對確定它是NP難），但有效且快速的近似就足夠了。

問題：給定正整數值的列表中找到最少數量的含整數的整個列表的不相交子集，其中每個子集款項小於N.顯然，在原始列表沒有整數可以是大於N.

在我的應用程序中，我有很多列表，我可以將它們連接成一個矩陣的列，只要它們適合矩陣在一起。對於下游目的，我希望在所得的不齊整的矩陣中具有儘可能少的「浪費」空間，因此空間填充相似性。

到目前爲止，我使用了一種類似貪婪的方法，從最大整數向下處理，找到適合當前子集的最大整數，一旦最小整數不再適合當前子集，我繼續直到所有數字都用盡爲止，直到下一個子集。這幾乎肯定無法找到最佳解決方案，但卻是我能夠迅速提出的最佳解決方案。

BONUS：我的應用程序實際上需要批次，每個批次（M）中的子集數量都有限制。因此，更大的問題是找出最少批次，其中每個批次包含M個亞羣，每個子集款項小於N.

Answer 1

直接從維基百科（有一些大膽的修改）：

在裝箱問題中，對象[整數]的不同體積[值]必須被 打包成一個有限數目個二進制位[套]或每體積V [求和子集< V的]在 的容器一種最小化使用的垃圾箱數量的方法[套件]。在計算複雜性理論中，它是一個組合NP難題。

https://en.wikipedia.org/wiki/Bin_packing_problem

據我所知，這正是你所期待的。