动态规划解决部分和问题（java）

韩冰发布于2019-08-15 17:44 / 1764人阅读

摘要：题目晓萌希望将到的连续整数组成的集合划分成两个子集合，且保证每个集合的数字和是相等。输出包括一行，仅一个整数，晓萌可以划分对应的集合的方案的个数。也就是本题可以转化为部分和问题，即前个数的和能凑成的有多少种。注意的是和为一种。

题目：晓萌希望将1到N的连续整数组成的集合划分成两个子集合，且保证每个集合的数字和是相等。例如，对于N=3，对应的集合{1，2，3}能被划分成{3} 和 {1,2}两个子集合.

这两个子集合中元素分别的和是相等的。

对于N=3，我们只有一种划分方法，而对于N=7时，我们将有4种划分的方案。

输入包括一行，仅一个整数，表示N的值（1≤N≤39）。

输出包括一行，仅一个整数，晓萌可以划分对应N的集合的方案的个数。当没发划分时，输出0。

样例输入

7
样例输出

分析：划分成两部分，那么这两部分的值也就是可以确定的，值为N! / 2。

  所以N! 只有是偶数的话才可分。
  也就是本题可以转化为部分和问题，即前N个数的和能凑成N! / 2的有多少种。
  注意的是 {1, 2} {3}和{3} {1, 2}为一种。
  设 dp[i][j]前i个数的部分和可以凑成j的子集数
  动态转移方程：
  当j >= arr[i - 1]时 dp[i][j] = dp[i - 1][j - arr[i - 1]] + dp[i - 1][j]
  其他： dp[i][j] = dp[i - 1][j]

代码实例：

        Scanner read = new Scanner(System.in);
        int N = read.nextInt();
        int sum = N * (N + 1)/ 2;
        if((sum & 1) == 1)// 如果和为奇数时  不可分
            System.out.println("0");
        else{
            // dp[i][j] 前i个数的部分和可以凑成j的子集数
            long[][] dp = new long[N +1][(sum / 2) + 1];
            //0可以凑成0
            dp[0][0] = 1;
            for(int i = 1; i <= N; ++i){
                for(int j = 0; j <= sum / 2; ++j){
                    if(j >= i){//当j >= arr[i - 1]时  dp[i][j] = dp[i - 1][j - arr[i - 1]] + dp[i - 1][j];
                        dp[i][j] = dp[i - 1][j - i] + dp[i - 1][j];
                    }else{//其他： dp[i][j] = dp[i - 1][j];
                        dp[i][j] = dp[i - 1][j];
                    }
                }
            }
            // 计数过程中类似的  {1, 2} {3}和{3} {1, 2} 会被重复记录 所以除2
            System.out.println(dp[N][sum / 2] / 2);
        }

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/69416.html

基本算法思想：递归+分治+动态规划+贪心+回溯+分支限界

摘要：代码实现见下面评论对应代码动态规划基本思想和分治法基本思想有共同的地方，不同的是子问题往往不是独立的，有事母问题要借助子问题的解来判断，因此把已经计算好的问题记录在表格中，后续如果需要查询一下，可以避免重复计算，这是动态规划的基本思想。作者：心叶时间：2018-05-01 19:28 本文对应github地址：https://github.com/yelloxing/... 以上实现...

EscapedDog 2019-08-26 11:52 评论0 收藏0
Java面试 32个核心必考点完全解析

摘要：如问到是否使用某框架，实际是是问该框架的使用场景，有什么特点，和同类可框架对比一系列的问题。这两个方向的区分点在于工作方向的侧重点不同。 [TOC] 这是一份来自哔哩哔哩的Java面试Java面试 32个核心必考点完全解析（完）课程预习 1.1 课程内容分为三个模块基础模块：技术岗位与面试计算机基础 JVM原理多线程设计模式数据结构与算法应用模块：常用工具集 ...

JiaXinYi 2019-08-16 16:53 评论0 收藏0
大厂算法面试之leetcode精讲3.动态规划

摘要：动态规划问题一定会具备最优子结构，才能通过子问题的最值得到原问题的最值。另外，虽然动态规划的核心思想就是穷举求最值，但是问题可以千变万化，穷举所有可行解其实并不是一件容易的事，只有列出正确的状态转移方程才能正确地穷举。大厂算法面试之leetcode精讲3.动态规划视频教程（高效学习）:点击学习目录：1.开篇介...

番茄西红柿 2021-11-22 14:56 评论0 收藏2637
动态规划入门（以爬楼梯为例）

摘要：动态规划算法通常基于一个递推公式及一个或多个初始状态。动态规划有三个核心元素最优子结构边界状态转移方程我们来看一到题目题目有一座高度是级台阶的楼梯，从下往上走，每跨一步只能向上级或者级台阶。概念动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。动态规划算法通常基于一个递推公式及一个或多个初始状态...

cyixlq 2019-08-23 10:52 评论0 收藏0