Data Structure
Networking
RDBMS
Operating System
Java
MS Excel
iOS
HTML
CSS
Android
Python
C Programming
C++
C#
MongoDB
MySQL
Javascript
PHP
Physics
Chemistry
Biology
Mathematics
English
Economics
Psychology
Social Studies
Fashion Studies
Legal Studies分配問題
對於此問題，可以對給定集合進行劃分，從而使每個子集之和相等。
首先，我們必須找出給定集合之和。如果為偶數，則存在將其分為兩組的可能性。否則，則無法分割。
對於偶數和值，我們將建立一個名為 partTable 的表，現在使用以下條件來解決問題。
當子集 array[0] 到 array[j-1] 的和等於 i 時，partTable[i, j] 為 true，否則為 false。
輸入和輸出
Input:
A set of integers. {3, 1, 1, 2, 2, 1}
Output:
True if the set can be partitioned into two parts with equal sum.
Here the answer is true. One pair of the partitions are: {3, 1, 1}, {2, 2, 1}演算法
checkPartition(set, n)
輸入 - 給定集合、集合中的元素數。
輸出 - 當分割槽可能產生和相等的兩個子集時返回 true。
Begin sum := sum of all elements in the set if sum is odd, then return define partTable of order (sum/2 + 1 x n+1) set all elements in the 0th row to true set all elements in the 0th column to false for i in range 1 to sum/2, do for j in range 1 to n, do partTab[i, j] := partTab[i, j-1] if i >= set[j-1], then partTab[i, j] := partTab[i, j] or with partTab[i – set[j-1], j-1] done done return partTab[sum/2, n] End
示例
#include <iostream>
using namespace std;
bool checkPartition (int set[], int n) {
int sum = 0;
for (int i = 0; i < n; i++) //find the sum of all elements of set
sum += set[i];
if (sum%2 != 0) //when sum is odd, it is not divisible into two set
return false;
bool partTab[sum/2+1][n+1]; //create partition table
for (int i = 0; i <= n; i++)
partTab[0][i] = true; //for set of zero element, all values are true
for (int i = 1; i <= sum/2; i++)
partTab[i][0] = false; //as first column holds empty set, it is false
// Fill the partition table in botton up manner
for (int i = 1; i <= sum/2; i++) {
for (int j = 1; j <= n; j++) {
partTab[i][j] = partTab[i][j-1];
if (i >= set[j-1])
partTab[i][j] = partTab[i][j] || partTab[i - set[j-1]][j-1];
}
}
return partTab[sum/2][n];
}
int main() {
int set[] = {3, 1, 1, 2, 2, 1};
int n = 6;
if (checkPartition(set, n))
cout << "Given Set can be divided into two subsets of equal sum.";
else
cout << "Given Set can not be divided into two subsets of equal sum.";
} 輸出
Given Set can be divided into two subsets of equal sum.
更新時間: 2020 年 6 月 17 日
1K+ 瀏覽
廣告