สมมติว่าเรามีอาร์เรย์ที่ไม่ว่างซึ่งมีเฉพาะตัวเลขที่เป็นบวก เราต้องค้นหาว่าอาร์เรย์นั้นสามารถแบ่งออกเป็นสองชุดย่อยได้หรือไม่ เพื่อให้ผลรวมขององค์ประกอบในชุดย่อยทั้งสองเท่ากัน ดังนั้นหากอินพุตเป็น [1,5,11,5] เอาต์พุตจะเป็นจริง เนื่องจากอาร์เรย์นี้สามารถแบ่งพาร์ติชันเป็น [1, 5, 5] และ [11]
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- n :=ขนาดของอาร์เรย์
- ผลรวม :=0
- สำหรับ i :=0 ถึง n – 1
- sum :=sum + nums[i]
- ถ้าผลรวมเป็นเลขคี่ ให้คืนค่าเท็จ
- sum :=sum / 2
- สร้างหนึ่งอาร์เรย์ที่เรียกว่า dp ของขนาดรวม + 1
- dp[0] :=จริง
- สำหรับ i ในช่วง 0 ถึง n – 1
- x :=nums[i]
- สำหรับ j :=รวมลงไป j – x
- dp[j] :=dp[j] หรือ dp[j - x] ซึ่งไม่ใช่ 0
- ส่งคืน dp[sum]
ตัวอย่าง(C++)
ให้เราดูการใช้งานต่อไปนี้เพื่อทำความเข้าใจ −
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool canPartition(vector<int>& nums) {
int n = nums.size();
int sum = 0;
for(int i =0;i<n;i++)sum+=nums[i];
if(sum&1)return false;
sum/=2;
vector <bool> dp(sum+1);
dp[0] = true;
for(int i =0;i<n;i++){
int x = nums[i];
for(int j =sum;j-x>=0;j--){
dp[j]=dp[j] || dp[j-x];
}
}
return dp[sum];
}
};
main(){
Solution ob;
vector<int> v = {1,5,11,5};
cout << ob.canPartition(v);
} อินพุต
[1,5,11,5]
ผลลัพธ์
1
