416.分割等和子集
給定一個只包含正整數的非空陣列，是否可以將這個陣列分割成兩個子集，使得兩個子集的元素和相等，
注意:
每個陣列中的元素不會超過 100
陣列的大小不會超過 200
示例 1:
輸入:
[1, 5, 11, 5]
輸出:
true
解釋: 陣列可以分割成 [1, 5, 5] 和 [11].
示例 2:
輸入:
[1, 2, 3, 5]
輸出:
false
解釋: 陣列不能分割成兩個元素和相等的子集.
思路：
先判斷總數是否是偶數，確定背包容量，然后遍歷判斷背包容量是否夠大，不夠大當前狀態則取決于上一個狀態，夠大則將背包容量減少，即將該元素放入背包中，再判斷狀態，
代碼：
class Solution
{
public:
bool canPartition(vector<int> &nums)
{
int tar = 0, n = nums.size();
for (int i = 0; i < n; i++)
tar += nums[i];
if (tar % 2 != 0) //判斷總和是否是偶數
return false;
tar /= 2; //每個子集的和
vector<bool> dp(tar + 1, false);
dp[0] = true; //database
for (int i = 0; i < n; i++)
{
for (int j = tar; j >= 0; j--) //反向遍歷，保證每個元素只使用一次
{
if (j - nums[i] >= 0)
{
dp[j] = dp[j] || dp[j - nums[i]];
}
}
}
return dp[tar];
}
};
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/189587.html
標籤：其他