【dp

样例：4
2
3
1
65
3
2
5
8
13

首先看到这道题，好简单的样子
然而。。。
第一步，想不出来正解先暴力 然后我暴力打爆了 然后。。。就真的爆了

我想的是暴搜两人相等的钱数是多少
其实我想错了 暴搜的话也不能只搜两人相等的钱数 因为剩下那一堆不一定凑得出来这个数
每一张钱有三种情况：给甲，给乙，两人都不拿

好 暴搜就说到这里
然后 d p dp dp 其实 d p dp dp我觉得是与暴搜有关联的 联系一下 我们先考虑定义这样的状态：
d p [ i ] [ j ] [ k ] dp[i][j][k] dp[i][j][k]:前i张钱 一堆为j 一堆为k这个方案是否可行（01状态） 答案就是 d p [ n ] [ x ] [ x ] dp[n][x][x] dp[n][x][x]为1的最大的x

显然这种状态是对的
但是 这个状态是不优的
在遇到一些两堆差值相等的时候 比如：
1 4
3 6
如果我们找到一组数使得1 4相等 比如说：5 2
那么5 2也一定能使3 6变得相等
而我们要求最大 那么1 4这个状态是没有贡献的 所以我们要去掉这些多余的状态 只保留最大的

所以我们定义 d p [ i ] [ j ] dp[i][j] dp[i][j]为：i张钞票分成两堆 这两堆的差值为j时 这两堆的和的最大值

转移的时候 从 i − 1 i-1 i−1的状态转移过来 对于第 i i i张钞票 考虑三种情况：给甲，给乙，两人都不拿 依次进行转移

注意：dp一定要搞清楚状态之间的关系 填表是站在过去看现在 刷表是站在现在看将来

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
#define MAXN 505
#define MAXS 100005
#define LL long long
int n,sum,ans;
int c[MAXN];
int dp[MAXN][MAXS];
int Abs(int x)
{if(x>=0) return x;return -x;
}
//dp[i][j]前i张钞票分成两堆 这两堆的差值为j时 这两堆的和的最大值 
//对于每个i 三种情况：给甲，给乙，两人都不拿
int main()
{freopen("kas.in","r",stdin);freopen("kas.out","w",stdout);scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&c[i]);sum+=c[i];}memset(dp,-0x3f,sizeof(dp));dp[0][0]=0;for(int i=1;i<=n;i++)for(int j=0;j<=sum;j++){dp[i][j]=dp[i-1][j];//不拿现：i状态dp[i][j]=max(dp[i][j],dp[i-1][j+c[i]]+c[i]);//这一张给较小的dp[i][j]=max(dp[i][j],dp[i-1][Abs(j-c[i])]+c[i]);//这一张给较大的//看起来是不是感觉反了 明明给较大的差值才会变成j+c[i]//但注意这里是填表法 是过去的差值为j+c[i] 这里可以结合画的图理解一下//dp[i][j]是已完成 dp[i-1][]是未完成(还没有分钱) //我们是用过去的值更新现在 而不管将来的差值是j+c[i] dp一定要搞清楚状态之间的关系//填表是站在过去看现在 刷表是站在现在看将来 }printf("%d\n",sum-dp[n][0]/2);return 0;
}

画的图：

关于另外一种刷表法，放一段代码参考一下吧
个人觉得 填表要反过来 不好想却代码简洁
刷表是顺水推舟的思路 好想但代码考虑得更多

（这个代码的状态定义略有些不同 dp[i][j]前i张钞票分成两堆 这两堆的差值为j时 这两堆中较大的那一个（其实这两种状态定义是一样的 都是可以互推的

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAXN 505
#define MAXS 100005
int n,sum;
int c[MAXN];
int dp[MAXN][MAXS];
int main()
{freopen("kas.in","r",stdin);freopen("kas.out","w",stdout);scanf("%d",&n);for(int i=1;i<=n;i++) {scanf("%d",&c[i]);sum+=c[i];}memset(dp,-1,sizeof(dp));dp[0][0]=0;for(int i=1;i<=n;i++)for(int j=0;j<=sum;j++) {if(dp[i-1][j]!=-1)dp[i][j+c[i]]=max(dp[i-1][j]+c[i],dp[i][j+c[i]]);dp[i][j]=max(dp[i-1][j],dp[i][j]);if(dp[i-1][j]!=-1) {if(c[i]>j)dp[i][c[i]-j]=max(dp[i][c[i]-j],dp[i-1][j]+c[i]-j);elsedp[i][j-c[i]]=max(dp[i][j-c[i]],dp[i-1][j]);}}printf("%d\n",sum-dp[n][0]);
}