部分和问题

描述

给定整数a1、a2、.......an，判断是否可以从中选出若干数，使它们的和恰好为K。

输入

首先，n和k，n表示数的个数，k表示数的和。
接着一行n个数。
（1<=n<=20,保证不超int范围）

输出

如果和恰好可以为k，输出“YES”，并按输入顺序依次输出是由哪几个数的和组成，否则“NO”

样例输入

4 13
1 2 4 7

样例输出

YES
2 4 7

---

　　这是一道相当简单的DFS类型的题目，从第一个数开始按顺序进行选择是否加入到Sum中，然后再判断Sum是否满足目标值，如果小于目标值则继续对下一个数进行相同的判断；如果大于目标值则直接剪枝，返回false；如果等于目标值则返回true。

源码：

 

 1  private static boolean find_DFS(int[] nums, int target, int sum, int index) {
 2         if (sum > target) {
 3             return false;//剪枝操作
 4         }
 5         if (sum == target) {
 6             return true;//找到目标值
 7         }
 8         if (index >= nums.length) {
 9             return false;//注意越界
10         }
11 
12         //选择当前的数字
13         boolean a = find_DFS(nums, target, sum + nums[index], index + 1);
14         //不选择当前的数字
15         boolean b = find_DFS(nums, target, sum, index + 1);
16         return a || b;
17         
18     }

 

　　该方法虽然进行了一些剪枝的处理，但在最坏的情况下算法的时间复杂度是O（2^n），即指数级的时间复杂度，所以我就想能不能使用DP？

　大家注意这一段代码：

 　　　　　　//选择当前的数字
13         boolean a = find_DFS(nums, target, sum + nums[index], index + 1);
14         //不选择当前的数字
15         boolean b = find_DFS(nums, target, sum, index + 1);

　　这和0-1背包问题十分类似，因此这题我们还可以使用DP来进一步优化复杂度，将O（2^n）降为O（N^2）。

下面给出了代码：

private static boolean find_DP(int[] nums, int k) {
        if (k == 0) {
            return true;
        }
        int len = nums.length;
        if (len == 0) {
            return false;
        }

        boolean[][] dp = new boolean[len + 1][k + 1];//k表示目标值，不断递增
        dp[0][0] = true;//当k为0的时候肯定满足

        for (int i = 1; i <= len; i++) {
            //i表示num中的每一个数字
            for (int j = 0; j <= k; j++) {//当前的目标值
                dp[i][j] |= dp[i - 1][j];//不选择当前的数字
                if (j >= nums[i - 1]) {
                    dp[i][j] |= dp[i - 1][j - nums[i - 1]];//选择当前的数字
                }


            }
        }
        return dp[len][k];
    }

 

 

 

部分和问题

原文：http://www.cnblogs.com/Yaser-WYX/p/6803532.html