01背包面試題系列（一）
題目描述——分割等和子集
給你一個 只包含正整數 的 非空 陣列
nums，請你判斷是否可以將這個陣列分割成兩個子集，使得兩個子集的元素和相等，示例 1：
輸入：nums = [1,5,11,5] 輸出：true 解釋：陣列可以分割成 [1, 5, 5] 和 [11] ，示例 2：
輸入：nums = [1,2,3,5] 輸出：false 解釋：陣列不能分割成兩個元素和相等的子集，
01背包動態規劃求解
上面的問題乍一看好像是一個子集劃分的問題，我們可能根據資料nums得到它的所有的子集，然后將所有的自己加起來看看是否存在一個子集的資料的和等于nums陣列所有資料的和的一半，其實我們確實可以這樣做，我們將在后文當中仔細探討這個方法，
那么我們改如何使用01背包去解決這個問題呢？我們首先先回顧一下01背包解決了什么問題：
有 \(N\)件物品和一個容量是 \(V\) 的背包，每件物品只能使用
一次，第\(i\)件物品的體積是\(v_i\)，價值是 \(w_i\)，求解將哪些物品裝入背包，可使這些物品的總體積不超過背包容量，且總價值最大，
01背包就是給定一定容量的背包，看他能夠裝入物品的最大的價值，那么我們該如何將上述問題轉化成01背包呢？
我們可以這樣，將nums陣列當中的數值變成物品對應的價值和體積，比如說nums = [1, 2, 3]，我們就可以分成三個物品，這三個物品的體積和價值分別是1和1、2和2和3和3，我們背包的容量為V = (1 + 2 + 3) / 2，我們將nums陣列當中所有資料和的一半作為背包的容量，nums當中的數值就表示每一個物品的價值和體積，而且價值和體積都相等，如果我們能夠恰好裝滿背包就說明，存在一種物品的組合他的和為nums陣列當中資料的和的一半，
那么我們該如何判斷背包被恰好裝滿呢？我們知道背包問題求解的只是在背包容量一定的情況下，我們能夠獲取的最大的價值是多少，因此好像不能夠判斷背包是否裝滿！但是在上面轉化的程序當中物品的體積和價值是相等的，因為我們可以根據我們獲得的最大價值判斷，如果我們最終得到的收益等于背包的容量，那么說明背包被填滿了，也就是存在一種物品的組合我們能夠獲取的最大的價值等于陣列當中資料和的一半，因為物品的價值和體積相等，因此把背包填滿和獲取最大價值是等價的，
因此根據上面的分析，如果我們想用01背包去解決這個問題，我們可以將背包容量設定為nums陣列當中資料和的一半，物品的個數為陣列的長度，物品的價值和體積為陣列當中對應位置的值，然后進行01背包求解即可，
如果你還不是很了解01背包的話，可以先看這篇文章，該文章主要從0開始介紹了01背包問題，從二維陣列到滾動陣列再到一維陣列，優化程序層層遞進，帶你從原理到實戰完全掌握01背包問題，
因此我們的代碼如下（一維陣列優化）：
class Solution {
public boolean canPartition(int[] nums) {
int sum = 0;
for (int num : nums) {
sum += num;
}
if ((sum & 1) == 1) return false;
int t = sum / 2;
int[] dp = new int[t + 1];
for (int i = 0; i < nums.length; i++) {
for (int j = t; j >= nums[i]; j--) {
dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
}
}
return dp[t] == t;
}
}
子集劃分求解
我們知道任何一個集合的子集個數為\(2^n\)，其中\(n\)表示集合當中資料的個數，比如說集合\({1, 2}\)有如下子集（4個）：
\[\{空集\}, \{1\}, \{2\}, \{1, 2\} \]我們先思考一下\(2^n\)是怎么計算出來的！我們在生成子集的時候對于每一個資料都有選擇和不選擇兩種情況，這其實就變成了一個排列組合問題，在上面的例子當中1可選可不選（2），2可選可不選（2），因此總的集合個數為4，那么如果有n個資料的集合那么自己個數就等于：
\[2\times2\times2 \cdots = 2^n \]這個選擇情況的劃分如下圖所示：
而我們使用程式去計算一個集合的子集其實就是一個回溯的問題，分割等和子集的子集劃分的代碼如下：
public class Solution {
private int target;
public boolean canPartition(int[] nums) {
int sum = 0;
for (int num : nums) {
sum += num;
}
if ((sum & 1) == 1 ) return false;
// 我們最終的目標就是找到一個自己的和等于這個數
target = sum / 2;
return backTrace(-1, 0, nums);
}
/**
* @param curIndex 表示當前遍歷的陣列的位置
* @param curSum 當前集合所有資料的和
* @param nums 待遍歷的陣列
* @return
*/
public boolean backTrace(int curIndex, int curSum, int[] nums) {
if (curSum == target) return true;
// 這里是剪枝操作 如果當前的和已經大于目標值或者
// 遍歷的下標超過陣列的長度了就回傳 false 表示
// 這個分支沒有找到一個集合，集合當中的資料之和等于 target
else if (curSum > target || curIndex >= nums.length - 1) return false;
// 選擇某個資料
curSum += nums[curIndex + 1];
if (backTrace(curIndex + 1, curSum, nums))
return true;
// 不選擇某個資料 對應這回溯的操作
curSum -= nums[curIndex + 1];
return backTrace(curIndex + 1, curSum, nums);
}
}
我們知道動態規劃的時間復雜度為\(O(nm)\)，其中\(m\)表示nums陣列的和的一半，\(n\)表示陣列當中資料的個數，而這個使用生成子集的方法的話時間復雜度為\(O(2^n)\)，因此如果你再LeetCode上提交這個代碼會超時，
總結
本文主要給大家介紹分割等和子集這個題目，這個題目的即可以使用動態規劃進行求解也能使用回溯法進行求解，但是回溯法求解問題的時間復雜度太高，使用動態規劃求解的方法還是比較抽象，可能需要大家花時間好好琢磨一下，希望大家有所識訓，我是LeHung，我們下期再見！！！（記得點贊收藏哦！）
更多精彩內容合集可訪問專案：https://github.com/Chang-LeHung/CSCore
關注公眾號：一無是處的研究僧，了解更多計算機（Java、Python、計算機系統基礎、演算法與資料結構）知識，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/499524.html
標籤：其他