首页 > 专题系列 > 算法分析 > 动态规划12-划分问题
2014
05-26

动态规划12-划分问题

划分问题是指,有一个集合,判断是否可以把这个结合划分为总和相等的两个集合。

例如:
arr[] = {1, 5, 11, 5}
Output: true
这个数组可以划分为: {1, 5, 5} 和 {11}

arr[] = {1, 5, 3}
Output: false
无法划分为总和相等的两部分

如果划分后的两个集合总和相等,则原集合的总和肯定为偶数,假设为总和为sum。问题即为是否有子集合的总和为sum/2.

递归解决

设函数 isSubsetSum(arr, n, sum/2) 返回true如果存在arr的一个子集合的总和为 sum/2
isSubsetSum函数为分为下面两个子问题
1) 不考虑最后一个元素。问题递归到 isSubsetSum(arr, n-1. sum/2)
2) 考虑最后一个元素。问题递归到 isSubsetSum(arr, n-1. sum/2-arr[n])
上面两种情况有一个返回TRUE即可
isSubsetSum (arr, n, sum/2) = isSubsetSum (arr, n-1, sum/2) ||
isSubsetSum (arr, n-1, sum/2 – arr[n-1])

#include <iostream>
#include <stdio.h>

bool isSubsetSum (int arr[], int n, int sum)
{
   // 基本情况
   if (sum == 0)
     return true;
   if (n == 0 && sum != 0)
     return false;

   // 如果最后一个元素比sum大,就不考虑该元素
   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[] = {3, 1, 5, 9, 12};
  int n = sizeof(arr)/sizeof(arr[0]);
  if (findPartiion(arr, n) == true)
     printf("Can be divided into two subsets of equal sum");
  else
     printf("Can not be divided into two subsets of equal sum");
  return 0;
}

时间复杂度:最快情况为 O(2^n),即每个元素有选或不选的两种选择

动态规划

如果所有元素的总和sum不是特别大时可以用动态规划来解决。问题可以转化为 是否有子集合的总和为sum/2.
这里通过自下向上打表的方法来记录子问题的解, part[i][j] 表示对于子集合 {arr[0], arr[1], ..arr[j-1]} 其总和是否为i.

其实这个问题和01背包问题是一样的。背包的最大容量为sum/2,如果最大价值可以达到sum/2则返回TRUE。

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][n+1];

    for (i = 0; i <= n; i++)
      part[0][i] = true;

    for (i = 1; i <= sum/2; i++)
      part[i][0] = false;     

     for (i = 1; i <= sum/2; i++)  
     {
       for (j = 1; j <= n; j++)  
       {
         part[i][j] = part[i][j-1];
         if (i >= arr[j-1])
           part[i][j] = part[i][j] || part[i - arr[j-1]][j-1];
       }        
     }    

    /** //测试打表数据
     for (i = 0; i <= sum/2; i++)  
     {
       for (j = 0; j <= n; j++)  
          printf ("%4d", part[i][j]);
       printf("\n");
     } */

     return part[sum/2][n];
}

时间复杂度为 O(sum*n)


  1. 有两个重复的话结果是正确的,但解法不够严谨,后面重复的覆盖掉前面的,由于题目数据限制也比较严,所以能提交通过。已更新算法

  2. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮