動態規劃尋找兩個子集

Question

讓X,Y子集{1,...,100n}其中|X|=3n和|Y|=7n。找到X的子集和BY的子集，使得：兩者都不爲空，|A|=|B|和sum a_i = sum b_i。

• 有O(n^2)資金，我們可以設定\{1,...,100n\}（最大的一個是1+... +100n即使這個人是不可能的，因爲X和Y不包括所有數字）
• 有O(n)的基數（設置大小）爲每個總和（來自之前的項目符號）
• 我們可以有一個\{0,1\}（布爾值）的表格，其大小爲O(n) X O(n^2)，其中行代表基數，列代表數字。所以1意味着我們可以創建一個子集基數i和集合的總和j
• 第一行/列很容易計算，當然

現在基本上我需要遍歷所有單元格並更新他們每個單元格爲O(n)。所以我們最終的總體時間複雜度爲O(n^4)。

我該怎麼做？

我想我可以迭代它逐行;意思是，如果我想更新單元T[i,j]（意思是一個大小爲i的集合j），那麼我可以尋找一組大小爲i-1加上一些等於j的術語。

但是！這可能是我們已經在前面的集合（大小i-1）中使用了這個術語 - 問題！

Answer 1

你幾乎在那裏。你動態規劃應該包含另一個參數：

允許定義DP[K,J,I]是用凝聚到J第一I分量的大小K亞羣的數量。這種動態編程的想法是，對於集合中的每個元素i，我們檢查兩種情況 - 將其添加到我們的子集中，而不添加它。

DP[0,0,i] = 1 
DP[k,j,0] = 0 
DP[k,j,i] = DP[k-1,j-S[i],i-1] or DP[k,j,i-1]