準確k個整數的子集合？

以下是這些問題Subset sum problem和Sum-subset with a fixed subset size我想知道用於求解子集求和問題的一般算法，其中我們被迫使用完全k個整數，k < = n。準確k個整數的子集合？

Evgeny Kluev提到他會去使用k = 4的最優值，然後對k-4使用強力值方法，其餘的最優值。任何人都可以在這裏結合最優k = 4算法，通過強力方法來解釋他的意思嗎？

也許有人知道更好的一般解決方案？

來源

2012-03-23 Bober02

您是否需要多次應用算法？或者只是一組數字？如果它只是一組數字，我建議你手動使用數字來查看它們有什麼樣的模式，稀疏等等 – 2012-03-23 12:27:30

嗯，我只需要查找它一次，但它仍然是非平凡的。你需要確保你從數組中獲取k個元素，因此我的問題 – Bober02 2012-03-23 13:35:40

原始的動態規劃算法適用於一個小的擴展 - 除了記住部分和，還需要記住用於獲得總和的整數。

在原始算法，假設目標總和是M和有n整數時，將填充一個布爾n X M陣列A，其中A[i,m]爲真當且僅當總和m可以通過從第一拾取（任何數量的）來實現（假設從0開始索引）。

可以將其擴展到三維陣列n X M X k，其中有一個類似的屬性 - A[i,m,l]爲true當且僅當，總和m可以通過從第一i+1整數恰好l採摘來實現。

假設整數在陣列j[0..n-1]：

遞歸關係是非常相似的 - 場A[0,j[0],1]是真實的（你挑j[0]，越來越總和j[0] 1個INT（杜）），在A[0,*,*]其他領域都是假的在A[i+1,*,*]從A[i,*,*]派生領域也類似於原始算法：A[i+1,m,l]是真，如果A[i,m,l]是真實的（如果你可以從第一i整數挑m，那麼顯然你可以從第一i+1整數挑m），或者如果A[i, m - j[i+1], l-1]爲真（如果你選j[i+1]然後你增加j[i+1]的總和和1的整數）。

如果k較小，則顯然是有意義的跳過上述所有部分，只是迭代的k整數所有組合，並檢查他們的款項。 k<=4確實似乎是一個明智的門檻。

來源

2012-03-23 14:08:12

我想知道上面的比較如何：http://stackoverflow.com/questions/8916539/sum-subset-with-a-fixed-subset -size/8926458＃comment12539828_8926458 – Bober02 2012-03-23 22:43:05

準確k個整數的子集合？

回答

相關問題