基于动态规划算法实现数组分割

起源：

在师兄网易的面试题中，一BOSS提出以下问题。

对于一个非负整型数组，是否可以用=，+，-负号串起来。

问题分析：

存在数组用=，+，-串起来。

即是否能把数组成员分割成两部分切相等。

即是否存在数组中n个成员相加等于数组成员综合的一半。

算法解析：

数组： A[size] 数组和： Sum

先判断如果数组和Sum等于奇数，则数组不可以用=，+，-负号串起来。

如果数组和为偶数，则如下：

构建矩阵： M[size+1][Sum+1]

M[i][k]: 如果在数组的前i个元素中，存在组合使得其和为k,则M[i][k]值为1.

否则M[i][k]的值为0.

动态规划的条件：

如果M[i][k]=1，则M[i+1][k]=1且M[i+1][k+A[i+1]]=1

最终得到矩阵M[size+1][Sum+1],如果M[size][Sum/2]的值为一，则数组可以分割成相等的两部分。

代码实现：

  1 #include "stdafx.h"
  2 #include "stdlib.h"
  3 #include <stack>
  4 using namespace std;
  5 
  6 bool isSubsetSplit(int A[], int len, int sum, stack<int> &st)
  7 {
  8 
  9     int **X = (int **)malloc((len + 1)*sizeof(int *));
 10 
 11     for (int idx = 0; idx <= len; idx++)
 12     {
 13         X[idx] = (int *)malloc((sum + 1)*sizeof(int));
 14         for (int m = 0; m <= sum; m++)
 15         {
 16             X[idx][m] = 0;
 17         }
 18     }
 19 
 20 
 21     X[0][0] = 1;
 22     for (int i = 1; i <= sum; i++)
 23     {
 24         X[0][i] = 0; //??0?0?????????? 1.2.3...sum??????0;
 25     }
 26 
 27     for (int j = 1; j <= len; j++)
 28     {
 29         X[j][0] = 1; //???j???j???????????0?????1 ???j???j??????????????0
 30     }
 31 
 32     for (int i = 1; i <= len; i++) //loop?????????????
 33     {
 34         for (int j = 1; j <= sum; j++) //loop?1?sum
 35         {
 36             if (X[i - 1][j])
 37                 X[i][j] = 1;
 38             for (int k = 1; k < i; k++)
 39             {
 40                 if (X[k][j])
 41                 {
 42                     X[i][j + A[i]] = 1;
 43                 }
 44             }
 45 
 46         }
 47         X[i][A[i]] = 1;
 48     }
 49 
 50 
 51 
 52     bool found = false;
 53     int curSum = sum / 2;
 54     if (X[len][curSum] == 1)
 55     {
 56         for (int i = len - 1; i >= 0; i--)
 57         {
 58             if (X[i][curSum] != 1)
 59             {
 60                 st.push(A[i + 1]);
 61                 curSum -= A[i + 1];
 62             }
 63         }
 64 
 65         found = true;
 66     }
 67     for (int j = 0; j <= len; j++)
 68     {
 69         for (int i = 0; i <= sum; i++){
 70             printf("%d",X[j][i]);
 71         }
 72         printf("
");
 73     }
 74 
 75     for (int idx = 0; idx <= len; idx++)
 76     {
 77         free(X[idx]);
 78     }
 79     free(X);
 80 
 81     if (found)
 82         return true;
 83 
 84     return false;
 85 }
 86 
 87 
 88 int _tmain(int argc, _TCHAR* argv[])
 89 {
 90     int Array[] = { 0, 1, 7, 4, 6, 3, 9, 2 };
 91 
 92     stack<int> st;
 93 
 94     bool bSplit = isSubsetSplit(Array, 7, 32, st);
 95     printf("%d",bSplit);
 96     char m =getchar();
 97     
 98 
 99     return 0;
100 }

View Code

总结，如果数组非正可负，是否可以如上实现？

其实也是可以的，只需把所有的负数去掉负号，然后从上即可。

具体为什么，留给大家，相信可以理解的。