【动态规划】01背包问题：猫狗大战

一堆数分两组
（1）每组数的个数只能差一个
（2）每组数之和的差值尽可能小
输入：n，n个数
输出：每组数之和

01背包：

所有数之和为sum,如果想让两组数之和相差尽可能小，那么两组数尽量靠近sum/2

数是偶数，选n/2个数，并且容量为sum/2，使价值最大
数是奇数，选n/2个数，并且容量为sum/2，是价值最大
所以，在n个数中，选n/2个数，使它们之和最大且不超过sum/2

dp[i][j][k]:从前i个数中选k个数使它们之和不超过j并且最大
dp[i][j][k]=max(dp[i-1][j][k],dp[i-1][j-w[i]][k-1]+w[i])
滚动数组：
dp[j][k]=max(dp[j][k],dp[j-w[i]][k-1]+w[i]) 

代码

#include
#include
using namespace std;
int n;
int w[201];
int dp[10000][201];
int main()
{
	memset(dp,0,sizeof(dp));
	cin>>n;
	int sum=0;
	for(int i=1;i<=n;i++){
		cin>>w[i];
		sum+=w[i];
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=sum/2;j>=w[i];j--){
			for(int k=1;k<=n/2;k++){
				dp[j][k]=max(dp[j][k],dp[j-w[i]][k-1]+w[i]);
			}
		}
	}
	cout<