Tổng tập hợp con bằng phân vùng trong C ++

Giả sử chúng ta có một mảng không rỗng chỉ chứa các số dương, chúng ta phải tìm xem mảng có thể được phân chia thành hai tập con sao cho tổng các phần tử trong cả hai tập con là như nhau. Vì vậy, nếu đầu vào là [1,5,11,5], đầu ra sẽ là true. Vì mảng này có thể được phân vùng thành [1, 5, 5] và [11]

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• n:=kích thước của mảng
• sum:=0
• for i:=0 to n - 1
  • sum:=sum + nums [i]
• nếu tổng là số lẻ, trả về false
• sum:=sum / 2
• tạo một mảng được gọi là dp có kích thước sum + 1
• dp [0]:=true
• cho tôi trong phạm vi từ 0 đến n - 1
  • x:=nums [i]
  • for j:=sum down to j - x
    • dp [j]:=dp [j] hoặc dp [j - x], không phải là 0
• trả về dp [sum]

Ví dụ (C ++)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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);
}

Đầu vào

[1,5,11,5]

Đầu ra

1