数据结构
网络
关系数据库管理系统 (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 次浏览
广告