首页 > 代码库 > 数组分割问题
数组分割问题
昨天同学问我一道关于数组分割的问题——有一个无序、元素个数为2n的正整数数组，要求：如何能把这个数组分割为元素个数为n的两个数组，并是两个子数组的和最接近。
假设2n个整数之和为sum。从2n个整数中找出n个元素的和，有三种可能：大于sum/2,等于sum/2，小于sum/2。可以考虑小于等于sum/2的情况。使用动态规划解决这个问题，其实这是一个NP问题，只能尽量去接近sum/2这个值。
我们可以定义dp[k][s]代表从前k个数中去任意个元素，且k小于等于n，其和为s是否存在；之所以将选出的数之和放在下标中，而不是作为dp[k]的值，是因为那种做法不满足动态规划的前提——最优化原理。
#include <iostream>#include <mem.h>using namespace std;const int MaxN = 100;const int maxSum = 100000;bool dp[MaxN][maxSum];int A[MaxN];int main(){ int n, k, i, s; cin >> n; for(i = 1; i <= 2*n; i++) { cin >> A[i]; } int sum = 0; for(i = 1; i <= 2*n; i++) sum += A[i]; memset(dp, false, sizeof(dp)); dp[0][0] = true; for(k = 1; k <= 2*n; k++) { for(i = min(k, n);i >= 1; i--) { for(s = 1; s <= sum/2; s++) { if(s >= A[k] && dp[i-1][s-A[k]]) dp[i][s] = true; } } } for(s = sum/2; s >= 1 && !dp[n][s]; s--); cout << "s1 = " << s << ";" << "s2 = " << sum - s << endl; return 0;}
数组分割问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。