子集和與一個整數(shù)相等算法

by Fabian Terh

由Fabian Terh

Previously, I wrote about solving the Knapsack Problem (KP) with dynamic programming. You can read about it here.

之前，我寫過有關(guān)使用動態(tài)編程解決背包問題(KP)的文章。 你可以在這里閱讀 。

Today I want to discuss a variation of KP: the partition equal subset sum problem. I first saw this problem on Leetcode — this was what prompted me to learn about, and write about, KP.

今天，我要討論KP的一種變體： 分區(qū)相等子集和問題 。 我首先在Leetcode上看到了這個問題-這就是促使我學(xué)習(xí)和撰寫KP的原因。

This is the problem statement (reproduced partially without examples):

這是問題說明(部分復(fù)制而沒有示例)：

Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.給定一個僅包含正整數(shù)的非空數(shù)組，請確定該數(shù)組是否可以劃分為兩個子集，以使兩個子集中的元素之和相等。

For the full problem statement, with constraints and examples, check out the Leetcode problem.

有關(guān)完整的問題說明(包括約束和示例)，請查看Leetcode問題 。

動態(tài)編程 (Dynamic programming)

Like with KP, we’ll be solving this using dynamic programming. Since this is a variation of KP, the logic and methodology is largely similar.

與KP一樣，我們將使用動態(tài)編程來解決此問題。 由于這是KP的變體，因此邏輯和方法學(xué)非常相似。

解 (Solution)

We will house our solution in a method that returns a boolean — true if the array can be partitioned into equal subsets, and false otherwise.

我們將解決方案包含在一個返回布爾值的方法中—如果可以將數(shù)組劃分為相等的子集，則返回true，否則返回false。

步驟1：防止奇數(shù)數(shù)組和 (Step 1: Guarding against odd array sum)

Trivially, if all the numbers in the array add up to an odd sum, we can return false. We only proceed if the array adds up to an even sum.

瑣碎地，如果數(shù)組中的所有數(shù)字加起來為奇數(shù)和，則可以返回false。 我們僅在數(shù)組加和為偶數(shù)時繼續(xù)進(jìn)行。

步驟2：建立表格 (Step 2: Creating the table)

Next, we create the table.

接下來，我們創(chuàng)建表。

Table rows represent the set of array elements to be considered, while table columns indicate the sum we want to arrive at. Table values are simply boolean values, indicating whether a sum (column) can be arrived at with a set of array elements (row).

表行表示要考慮的一組數(shù)組元素，而表列表示我們要達(dá)到的總和。 表值只是布爾值，指示是否可以通過一組數(shù)組元素(行)得出總和(列)。

Concretely, row i represents a set of array elements from indices 0 to (i-1). The reason for this offset of 1 is because row 0 represents an empty set of elements. Therefore, row 1 represents the first array element (index 0), row 2 represents the first two array elements (indices 0–1), and so on. In total, we create n + 1 rows, inclusive of 0.

具體而言，第i行代表從索引0到( i -1)的一組數(shù)組元素。 偏移量為1的原因是因?yàn)樾?代表一組空元素。 因此，第1行代表第一個數(shù)組元素(索引0)，第2行代表前兩個數(shù)組元素(索引0-1)，依此類推。 我們總共創(chuàng)建n + 1行，包括0。

We only want to know if we can sum up exactly to half the total sum of the array. So we only need to create totalSum / 2 + 1 columns, inclusive of 0.

我們只想知道是否可以精確地求和該數(shù)組總和的一半。 因此，我們只需要創(chuàng)建totalSum / 2 + 1列(包括0)即可。

步驟3：預(yù)先填寫表格 (Step 3: Pre-filling the table)

We can immediately begin filling the entries for the base cases in our table — row 0 and column 0.

我們可以立即開始在表中填充基本案例的條目-第0行和第0列。

In the first row, every entry — except the first — must be false. Recall that the first row represents an empty set . Naturally, we are unable to arrive at any target sum — column number — except 0.

在第一行中，除第一行外，每個條目都必須為false 。 回想一下，第一行代表一個空集。 自然，我們無法得出除0以外的任何目標(biāo)總數(shù)(列號)。

In the first column, every entry must be true. We can always,trivially, arrive at a target sum of 0, regardless of the set of elements we have to work with.

在第一列中，每個條目都必須為true 。 無論我們要使用什么元素集，我們總是可以輕松地達(dá)到目標(biāo)總和0。

步驟4：建立表格(問題的癥結(jié)) (Step 4: Building the table (the crux of the problem))

Some entry in the table at row i and column j is true (attainable) if one of the following three conditions are satisfied:

如果滿足以下三個條件之一，則第i行和第j列中表中的某些條目為true (可達(dá)到)：

the entry at row i-1 and column j is true. Recall what the row number represents. Therefore, if we are able to attain a particular sum with a subset of the elements that we have presently, we can also attain that sum with our current set of elements — by simply not using the extra elements. This is trivial. Let’s call this prevRowIsTrue.

第i -1行和第j列的條目為true 。 回憶一下行號代表什么。 因此，如果我們能夠使用當(dāng)前元素的一個子集獲得一個特定的總和，那么我們也可以使用我們當(dāng)前的元素集來獲得該總和-只需不使用額外的元素即可。 這是微不足道的。 我們將此prevRowIsTrue 。

The current element is exactly the sum we want to attain. This is also trivially true. Let’s call this isExactMatch.

當(dāng)前元素正是我們想要獲得的總和。 這一點(diǎn)也是正確的。 我們將此isExactMatch 。

If the above two conditions are not satisfied, we have one remaining way of attaining our target sum. Here, we use the current element — the additional element in the set of elements in our current row compared to the set of elements in the previous row — and check that we are able to attain the remainder of the target sum. Let’s call this canArriveAtSum.

如果不滿足上述兩個條件，則我們還有另一種方法來達(dá)到目標(biāo)??總和。 在這里，我們使用當(dāng)前元素(當(dāng)前行元素集中的上一個元素與前一行元素集相比的其他元素)，并檢查是否能夠達(dá)到目標(biāo)總和的其余部分。 我們將此canArriveAtSum 。

Let’s unpack condition 3. We can only use the current element if it is less than our target sum. If they’re equal, condition 2 would be satisfied. If it’s larger, we can’t use it. Therefore, the first step is to ensure that current element < target sum.

讓我們解壓縮條件3。 如果當(dāng)前元素小于目標(biāo)總和，我們只能使用它。 如果它們相等，則將滿足條件2。 如果更大，我們將無法使用。 因此，第一步是確保當(dāng)前元素<目標(biāo)總和。

After using our current element, we are left with the remainder of our target sum. We then check if that is attainable by checking the corresponding entry in the row above.

使用完當(dāng)前元素后，剩下剩下的目標(biāo)總和。 然后，我們通過檢查上一行中的相應(yīng)條目來檢查是否可以實(shí)現(xiàn)。

As with regular KP, we want to progressively build our table from the bottom-up. We start with the base cases, until we arrive at our final solution.

與常規(guī)KP一樣，我們希望從下至上逐步構(gòu)建表格。 我們從基本案例開始，直到得出最終解決方案。

步驟5：返回答案 (Step 5: Returning the answer)

We simply return return mat[nums.length][totalSum / 2].

我們只返回return mat[nums.length][totalSum / 2] 。

工作代碼 (Working code)

Thanks for reading!

謝謝閱讀！

翻譯自: https://www.freecodecamp.org/news/a-variation-on-the-knapsack-problem-how-to-solve-the-partition-equal-subset-sum-problem-in-java-7e0fc047f19b/

子集和與一個整數(shù)相等算法

總結(jié)

以上是生活随笔為你收集整理的子集和与一个整数相等算法_背包问题的一个变体：如何解决Java中的分区相等子集和问题...的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。