Question

Viết chương trình nhập vào một dãy số nguyên gồm N (1<=N<=500) phần tử A_1,A₂…A_N. Tìm cách chia mảng thành 2 đoạn có tổng các phần tử trong mỗi đoạn bằng nhau. C++, ai giup voi

Answer 1

#include <iostream>

#include <vector>

using namespace std;

bool divideArray(vector<int>& nums, int N) {

     int totalSum = 0;

     for (int i = 0; i < N; i++) {

          totalSum += nums[i];

     }

     if (totalSum % 2 != 0) {

          return false;

     }

     int halfSum = totalSum / 2;

     vector<vector<bool>> dp(N + 1, vector<bool>(halfSum + 1, false));

     dp[0][0] = true;

     for (int i = 1; i <= N; i++) {

          for (int j = 0; j <= halfSum; j++) {

               dp[i][j] = dp[i - 1][j];

               if (j >= nums[i - 1]) {

                    dp[i][j] = dp[i][j] || dp[i - 1][j - nums[i - 1]];

               }

          }

     }

     return dp[N][halfSum];

}

int main() {

     int N;

     cout << "Nhập số phần tử N: ";

     cin >> N;

     vector<int> nums(N);

     cout << "Nhập các phần tử của mảng: ";

     for (int i = 0; i < N; i++) {

          cin >> nums[i];

     }

     bool isPossible = divideArray(nums, N);

     if (isPossible) {

          cout << "Có thể chia mảng thành hai đoạn có tổng bằng nhau." << endl;

     } else {

          cout << "Không thể chia mảng thành hai đoạn có tổng bằng nhau." << endl;

     }

     return 0;

}