資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學C++中的劃分問題
在這個問題中，我們必須構建C++程式碼來確定陣列是否可以劃分成兩個相等的子陣列。此外，我們必須檢查條件，即兩個子陣列中所有元素的和是否完全相同。劃分問題是子集和問題的變體，而子集和問題又是揹包問題的變體。我們將使用C++程式語言來解決劃分問題。我們必須返回一個包含“Yes”或“No”的字串，具體取決於是否滿足指定的條件。
輸入
arr[] = {6, 4, 8, 12, 15}輸出
Is possible to divide into two subsets of equal sum
解決問題的方法
目標是找到集合中所有元素的和。當陣列總和為奇數時，我們無法將其分成兩個集合。當總和為偶數時，找到和為總和/2的子集。使用給定的陣列，逐個檢查每個元素，然後選擇以下選項之一：
繼續將當前項包含在子集中，然後新增其餘項以達到總和。
一旦當前項已從子集中移除，則對其他項重複此過程。
最後，如果當前項包含在子集中或從子集中排除，則返回true；否則，返回false。如果不再有項或總和變為負數，則遞迴終止。如果總和為0，則返回true，這意味著已識別出一個子集。
示例
#include <bits/stdc++.h>
using namespace std;
bool isSubsetSum(int arr[], int n, int sum) {
if (sum == 0)
return true;
if (n == 0 && sum != 0)
return false;
if (arr[n - 1] > sum)
return isSubsetSum(arr, n - 1, sum);
return isSubsetSum(arr, n - 1, sum) ||
isSubsetSum(arr, n - 1, sum - arr[n - 1]);
}
bool findPartiion(int arr[], int n) {
int sum = 0;
for (int i = 0; i < n; i++)
sum += arr[i];
if (sum % 2 != 0)
return false;
return isSubsetSum(arr, n, sum / 2);
}
int main() {
int arr[] = {
6,
4,
8,
12,
15
};
int n = sizeof(arr) / sizeof(arr[0]);
if (findPartiion(arr, n) == true)
cout << "Is possible to divide into two subsets " "of equal sum";
else
cout << "Is impossible to divide into two subsets" " of equal sum";
return 0;
}輸出
Is impossible to divide into two subsets of equal sum
方法2
當元素的總和不太大時，可以使用動態規劃來解決這個問題。可以建立一個大小為(sum/2 + 1)*(n+1)的二維陣列part[][]。我們也可以自底向上構建解決方案，這樣每個填充的條目都具有以下屬性。我們可以使用大小為(sum/2 + 1)*(n + 1)的二維陣列來解決這個問題，而不是大小為(sum/2 + 1)*(n + 1)的二維陣列。
示例
#include <bits/stdc++.h>
using namespace std;
bool findPartiion(int arr[], int n) {
int sum = 0;
int i, j;
for (i = 0; i < n; i++)
sum += arr[i];
if (sum % 2 != 0)
return false;
bool part[sum / 2 + 1];
for (i = 0; i <= sum / 2; i++) {
part[i] = 0;
}
for (i = 0; i < n; i++) {
for (j = sum / 2; j >= arr[i]; j--){
if (part[j - arr[i]] == 1 || j == arr[i])
part[j] = 1;
}
}
return part[sum / 2];
}
int main() {
int arr[] = {
6,
4,
8,
12,
15
};
int n = sizeof(arr) / sizeof(arr[0]);
if (findPartiion(arr, n) == true)
cout << "Is possible to divide into two subsets of equal " "sum";
else
cout << "Is impossible to divide into two subsets" " of equal sum";
return 0;
}輸出
Is impossible to divide into two subsets of equal sum
結論
在這個問題中，我們學習瞭如何解決劃分問題以及C++程式碼。這段程式碼也可以用Java、Python和其他語言編寫。我們已經使用C++程式語言中的遞迴陣列解決了劃分問題。這是一個基礎程式碼，但在解決問題方面有很多用途。
更新於：2022年3月7日
596 次瀏覽
廣告