第四节 子集总和 subset sum 精通C语言 递归算法和动态规划

 第四节 子集总和 subset sum

第一节 序 斐波那契数列         Fibonacci

第二节 0 1背包问题   0 1 Knapsack Problem

第三节 编辑距离         edit distance

第四节 子集总和         subset sum

第五节 钢条切割          cut rod

第六节 硬币找零          Coin Change

第七节 最长公共子序列         Longest Common Subsequence

第八节 矩阵链式乘法 Matrix Chain Multiplication

第九节 最优游戏策略 Optimal Strategy for a Game

第十节 最优二叉查找树         Optimal Binary Search Tree

第十一节 最长递增子序列 Longest Increasing Subsequence

        问题描述

给定一组非负整数和一个值sum，确定给定集合的子集是否等于sum。

        例子： 

输入： set [] = {3，34，4，12，5，2}，sum = 9

输出： True  

有一个总和为9的子集（4，5）。

输入： set [] = {3、34、4、12、5、2}，sum = 30

输出： False

没有子集总和为30。

递归解决方案

最优子结构：从数组的右侧向左扫描，考虑两种情况：

1.考虑最后一个元素，现在所需总和 = 目标总和 - “最后”元素的值；元素个数 = n - 1

2.不考虑“最后”元素，现在需要总和 = 目标总和；元素个数 = n- 1

Base Cases:

SubsetSum(set, n, sum) = false, if sum > 0 and n == 0

SubsetSum(set, n, sum) = true, if sum == 0

该解决方案的时间复杂度,最坏情况下 O(2^n).

int subsetsum (int set[], int n, int sum)

{

    if (sum == 0)

        return 1;

    if (n == 0) //n==0 && sum != 0

        return 0;

    

    if (sum < set[n - 1])

        return subsetsum(set, n-1, sum);

        

    return subsetsum(set, n-1, sum) ||

            subsetsum(set, n-1, sum - set[n-1]);

}

DP解决方案

创建一个大小为（n + 1）*（sum + 1）的2D数组，类型为boolean。

如果存在来自A [0….i]的元素子集且总和 = 'j'，则状态数组DP [i] [j]为真。该问题的解决方法是：

if (A[i-1] > j)

DP[i][j] = DP[i-1][j]

else 

DP[i][j] = DP[i-1][j] OR DP[i-1][j-A[i-1]]

该解决方案的时间复杂度为O(n*Sum).

int subsetsum(int set[], int n, int sum)

{

    int subset[n + 1][sum + 1];

    for (int i = 0; i <= n; i++)

        subset[i][0] = 1;

    for (int j = 0; j <= sum; j++)

        subset[0][j] = 0;

    for (int i = 1; i <= n; i++)

    {

        for (int j = 1; j <= sum; j++)

        {

            if (set[i - 1] > j)

                subset[i][j] = subset[i - 1][j];

            else

                subset[i][j] = subset[i - 1][j] || subset[i - 1][j - set[i - 1]];

        }

    }

    return subset[n][sum];

}