脚本宝典收集整理的这篇文章主要介绍了动态规划 解决部分和问题(java),脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
题目:晓萌希望将1到N的连续整数组成的集合划分成两个子集合,且保证每个集合的数字和是相等。例如,对于N=3,对应的集合{1,2,3}能被划分成{3} 和 {1,2}两个子集合.
这两个子集合中元素分别的和是相等的。
对于N=3,我们只有一种划分方法,而对于N=7时,我们将有4种划分的方案。
输入包括一行,仅一个整数,表示N的值(1≤N≤39)。
输出包括一行,仅一个整数,晓萌可以划分对应N的集合的方案的个数。当没发划分时,输出0。
样例输入
7
样例输出
4
分析: 划分成两部分,那么这两部分的值也就是可以确定的,值为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); }
以上是脚本宝典为你收集整理的动态规划 解决部分和问题(java)全部内容,希望文章能够帮你解决动态规划 解决部分和问题(java)所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。