power oj 2784: ​上决╇ф人员分配问题

https://www.oj.swust.edu.cn/problem/show/2784
刚看到以为是背包，结果两边选的个数要一样多。。。就不能背包了。。。
然后问同学。。。
哎，dp题真不知道他们是怎么想到的0.0
dp[i][j][k] $dp\left[i\right]\left[j\right]\left[k\right]$表示在前 i $i$个物品中选 j $j$个的战斗力为 k $k$的情况是不是有
转移方程就是：
dp[i][j][k]=dp[i−1][j][k] $dp\left[i\right]\left[j\right]\left[k\right]=dp[i-1]\left[j\right]\left[k\right]$| dp[i−1][j−1][k−a[i]]; $dp[i-1][j-1][k-a[i\left]\right];$

这一个物品不选那么上一次状态就是：在 i−1 $i-1$个物品中选了 j $j$个（因为这一次没有在上一次的状态上增加），总战斗力为 k $k$的情况（因为还是那k个，所以战斗力不变）

而这一个物品选的上一次状态就是：在 i−1 $i-1$个物品中选 j−1 $j-1$个（因为这次要选一个），总价值为 k−a[i] $k-a\left[i\right]$的情况（因为这次的是 a[i] $a\left[i\right]$，所以以前的要 k−a[i] $k-a\left[i\right]$才行）

/* 再用滚动数组优化 */
#include"iostream"
#include"bitset"
using namespace std;
bool dp[2][16][45000];
int a[31];
int N;
int abss(int n)
{
    if(n<0)return -n;
    else return n;
}
int main()
{
    while(cin>>N)
    {
        dp[0][0][0]=1;
        int sum=0;
        for(int i=1;i<=2*N;i++)
        {
            cin>>a[i];
            sum+=a[i];
        }
        int pre=0,now=0;
        for(int i=1;i<=2*N;i++)
        {
            now=pre^1;
            for(int j=1;j<=N;j++)
            {
                for(int k=1;k<=sum;k++)
                {
                    if(k>=a[i])dp[now][j][k]=dp[pre][j][k]|dp[pre][j-1][k-a[i]];
                    else dp[now][j][k]=dp[pre][j][k];
                }
            }
            pre=now;
        }
        int ans=1e9;
        for(int i=0;i<=sum;i++)
        {
            if(dp[now][N][i])
            {
                ans=min(ans,abss(sum-i-i));
            }
        }
            cout<<ans<<endl;
    }
}