POJ1015 Jury Compromise（Jan. 18th, 2019） 背包方案输出

// La Pluie
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 200 + 5, M = 20 + 5;
struct PLUIE{
    int p/*lus*/, s/*ubtract*/, t/*otal*/, d/*ifference*/;
} pluie[N];
int n, m, res_p, res_s, ans[M], dp[M][N << 2];
// dp[i][j] stands for the situation that i people are chosen and now the difference of the remark is j.
vector <int> link[M][N << 2];
void INPUT(){
    for(int i = 1; i <= n; i++){
        int a, b, c, d;
        scanf("%d %d", &a, &b);
        c = a + b, d = a - b;
        pluie[i] = (PLUIE){a, b, c, d};
    }
}
void DFS(int k){
    for(int i = 0; i < link[m][k]. size(); i++)
        ans[i + 1] = link[m][k][i];
}
void SOLVE(){
    res_p = res_s = 0;
    int mov = 20 * m;
    for(int i = 1; i <= m; i++)
        for(int j = 0; j <= (mov << 1); j++)
            link[i][j]. clear();
    memset(dp, -1, sizeof(dp));
    dp[0][mov] = 0;
    for(int i = 1; i <= n; i++){ // Come to confirm the next one when the present one has been confirmed.
        for(int j = m; j > 0; j--){ // As 01 Package
            for(int k = 0; k < (mov << 1); k++){
                int lune = k - pluie[i]. d; // The difference of the previous situation.
                // pluie[i]. d stands for the difference of choosing the i-th person minus not choosing him.
                if(lune >= 0 && dp[j - 1][lune] >= 0 && dp[j][k] < dp[j - 1][lune] + pluie[i]. t){
                    dp[j][k] = dp[j - 1][lune] + pluie[i]. t;
                    link[j][k] = link[j - 1][lune]; // Copy the path.
                    link[j][k]. push_back(i); // Extend the path.
                }
            }
        }
    }
    for(int i = mov, j = mov; i >= 0; i--, j++){ // Equals to `for(int d = 0; d <= mov; d++) i = mov - d, j = mov + d` to search the one which is the closest to the zero point. Obviously, the first one found is the answer.
        if(dp[m][i] >= 0){
            if(dp[m][j] > dp[m][i]) DFS(j);
            else DFS(i);
            break;
        }
        if(dp[m][j] >= 0){
            DFS(j);
            break;
        }
    }
    for(int i = 1; i <= m; i++){
        res_p += pluie[ans[i]]. p;
        res_s += pluie[ans[i]]. s;
    }
}
void OUTPUT(int cnt){
    printf("Jury #%d\n", cnt);
    printf("Best jury has value %d for prosecution and value %d for defence:\n", res_p, res_s);
    for(int i = 1; i <= m; i++)
        printf(" %d", ans[i]);
    printf("\n\n");
}
int main(){
    int cnt = 0;
    while(~scanf("%d %d", &n, &m) && (n || m)){
        INPUT();
        SOLVE();
        OUTPUT(++cnt);
    }
    return 0;
}