背包DP

本题核心
1、动态规划记录方案—记录上一步决策
2、把差值存到数组维数里，P+D的和作为数组存储的值，就有最优子结构
3、把选出的人数作为背包的容量，最终要选出m人

#include<bits/stdc++.h>
using namespace std;
const int N = 205,M = 25,K = 805;
int n,m,T,p[N],d[N],f[M][K];
bool choose[N][M][K];
void print(int i,int j,int k)
{
    if(!j) return;
    if(choose[i][j][k+400])
    {
        print(i-1,j-1,k-(d[i]-p[i]));
        printf(" %d",i);
    }
    else print(i-1,j,k);
}
int main()
{
    while(cin>>n>>m&&n)
    {
        for(int i = 1;i<=n;i++) cin>>p[i]>>d[i];
        memset(f,0xcf,sizeof f);
        f[0][0+400] = 0;
        for(int i = 1;i<=n;i++)
            for(int j = m;j>=1;j--)
                for(int k = -20*m;k<=20*m;k++)
                {
                    choose[i][j][k+400] = 0;
                    if(k-(d[i]-p[i])<-20*m || k-(d[i]-p[i])>20*m) continue;
                    if(f[j][k+400] < f[j-1][k-(d[i]-p[i])+400]+d[i]+p[i])
                    {
                        f[j][k+400] = f[j-1][k-(d[i]-p[i])+400]+d[i]+p[i];
                        choose[i][j][k+400] = 1;
                    }
                }
        int d1 = 1<<30,d2,sum = 0,ansk;
        for(int k = -20*m;k<=20*m;k++)
            if(f[m][k+400] >= 0 && (abs(k) < d1 || abs(k)==d1 && f[m][k+400]>sum))
            {
                sum = f[m][k+400];
                d1 = abs(k);
                d2 = k;
                ansk = k;
            }
        // d+p = sum
        // d-p = d2
        printf("Jury #%d\n",++T);
        printf("Best jury has value %d for prosecution and value %d for defence:\n",(sum-d2)/2,(sum+d2)/2);
        print(n,m,ansk);
        printf("\n\n");
    }
    return 0;
}