拆分集合为两个和相等的子集合问题(动态规划)

看到此文,是否觉得体内洪荒之力爆发,饥渴难耐想吐槽、情不自禁想捐赠
本文为原创文章,尊重辛勤劳动,可以免费摘要、推荐或聚合,亦可完整转载,但完整转载需要标明原出处,违者必究。

支付宝微  信

题意

问题描述:将1到N的连续整数组成的集合划分为两个子集合,且保证每个集合的数字和相等。例如,对于N=4,对应的集合{1,2,3,4},能被划分为{1,4}、{2,3}两个集合,使得1+4=2+3,且划分方案只有此一种。编程实现给定任一正整数N(1<=N<=39),输出其符合题意的划分方案数。

样例输入1:3

样例输出1:1    (可划分为{1,2}、{3})

样例输入2:4

样例输出2:1    (可划分为{1,3}、{2,4})

样例输入3:7

样例输出3:4    (可划分为{1,6,7}、{2,3,4,5},或{1,2,4,7}、{3,5,6},或{1,3,4,6}、{2,5,7},或{1,2,5,6}、{3,4,7})

思路

根据动态规划思想,可以得到状态转移方程如下:

$d[$i][$j] = $d[$i - 1][$j] + $d[$i - 1][$j - $i];
// $i 取前$i个元素
// $j 取前$i个元素总和为$j
// $d[$i][$j] 取前$i个元素总和为$j的方案数

如果,对动态规划不理解建议看下这个视频:http://open.163.com/movie/2010/6/8/1/M6TCSIN1U_M6TCT9E81.html
状态转移方程:取$i个元素的方案数为$d[$i - 1][$j],不取第$i个元素的方案数为$d[$i - 1][$j - $i]。故将$i的问题递归为$i - 1的问题。符合动态规划的基本思想:
1. overlapping sub-problem(重叠子问题)
2. optimal sub-structure (最优子结构)

源码

方案一:

function t2($n) {
    $sum = ($n + 1) * $n / 2;
    if($sum % 2) {
        return 0;
    }
    $sum = $sum / 2;
    $t = array();
    for($i = 0; $i <= $n; $i++) {
        for($j = 0; $j <= $sum; $j++) {
            if($j == 0) $d[$i][$j] = 1; else $d[$i][$j] = 0;
        }
    }
    for($i = 1; $i <= $n; $i++) {
        for($j = 1; $j <= $sum; $j++) {
            $d1 = $d[$i - 1][$j];
            $d2 = $d[$i - 1][$j - $i];
            $d[$i][$j] = $d1 + $d2;
//          echo "i:{$i} j:{$j} d1(d[{$i} - 1][{$j}]):{$d1} d2(d[{$i} - 1][{$j} - {$i}]):{$d2}\n";
        }
    }
//  var_dump($d);
    return $d[$n][$sum] / 2; 
}

 

方案二:

<?php
function t($n) { 
    $sum = ($n + 1) * $n / 2; 
    if($sum % 2) { 
        return 0; 
    }   
    $sum = $sum / 2; 
    $d = array();
    $d[0] = 1;
    for($i = 1; $i <= $n; $i++) { 
        for($j = $sum; $j >= $i; $j--) {
//          echo "j:{$j} i:{$i}\n";
//          echo "the j - 1 is: {($j-$i)}\nthe d[j - i] is: {$d[$j - $i]}\n";
            $d[$j] += $d[$j - $i];
//          var_dump($d) . "\n\n";
        }   
    }   
//  echo "rs:" . var_dump($d);
    return $d[$sum] / 2;
}

可以看出第二种的优化相对于第一种在空间复杂度上有了很大的提升。
V = N * (N + 1) / 4
第一种:O(N * V) = O( N^2 * (N+1) / 4)
第二种:O(N)


建议参考文章:http://www.cnblogs.com/kangjianwei101/p/5332451.html

文章来源:胡旭个人博客 => 【原】拆分集合为两个和相等的两个子集合的问题(动态规划)

转载请注明出处,违者必究!


这是一篇原创文章,如果您觉得有价值,可以通过捐赠来支持我的创作~
捐赠者会展示在博客的某个页面,钱将会用在有价值的地方,思考中...


分类: PHP, 技术, 技术分享, 算法, 编程 | 标签: , , , , , | 评论 | Permalink

发表评论

电子邮件地址不会被公开。