PKU ACM 1015(Jury Compromise)的动态规划解法(JAVA实现)
package problem1015;import java.util.ArrayList;import java.util.Collections;import java.util.Scanner;public class Main {static int candidateNum;static int jurMemNum;static int [] sub;static int [] plus;static int totValRangeSize;static int totValDelta;/*F[i][j] means among i candidates, the maximum D(J) + P(J) while |D(J) - P(J)| = j F[i][j] = -1 if no J satisfy |D(J) - P(J)| = j within i candidates */static int [][] dp;static int [][] path;// index of the last candidate put in when updating dp[i][j]/** * @param args */public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int caseCtr = 0;while(true){caseCtr++;candidateNum = scanner.nextInt();jurMemNum = scanner.nextInt();if(candidateNum == 0 || jurMemNum == 0)break;sub = new int[candidateNum];plus = new int[candidateNum];for(int i = 0; i < candidateNum; i++){int pros = scanner.nextInt();int def = scanner.nextInt();sub[i] = pros - def;plus[i] = pros + def;}System.out.println("Jury #" + caseCtr);solve();}}static void solve(){totValRangeSize = 21 * jurMemNum * 2 + 1;totValDelta = 21 * jurMemNum;dp = new int[jurMemNum + 1][totValRangeSize];path = new int[jurMemNum + 1][totValRangeSize];for(int i = 0; i < jurMemNum + 1; i++){for(int j = 0; j < totValRangeSize; j++){dp[i][j] = -1;path[i][j] = -1;}}for(int i = 0; i < candidateNum; i++){if(plus[i] > dp[1][totValDelta + sub[i]]){dp[1][totValDelta + sub[i]] = plus[i];path[1][totValDelta + sub[i]] = i;}}//Bottom-Topfor(int i = 1; i < jurMemNum; i++){for(int j = 0; j < totValRangeSize; j++){if(dp[i][j] > -1){for(int k = 0; k < candidateNum; k++){if(dp[i][j] + plus[k] > dp[i + 1][j + sub[k]]){int index1 = i;int index2 = j;while(index1 != 0){if(k == path[index1][index2])break;index2 = index2 - sub[path[index1][index2]];index1--;}if(index1 == 0){dp[i + 1][j + sub[k]] = dp[i][j] + plus[k];path[i + 1][j + sub[k]] = k;}}}}}}for(int i = 0; i < totValDelta; i++){if(dp[jurMemNum][totValDelta - i] > -1 || dp[jurMemNum][totValDelta + i] > -1){if(dp[jurMemNum][totValDelta - i] > dp[jurMemNum][totValDelta + i])outputResult(totValDelta - i);elseoutputResult(totValDelta + i);break;}}}private static void outputResult(int val) {ArrayList<Integer> selected = new ArrayList<Integer>();int jurSize = jurMemNum;int totVal = val;int subSum = 0;int plusSum = 0;while(jurSize != 0){int candi = path[jurSize][totVal];selected.add(candi + 1);subSum += sub[candi];plusSum += plus[candi];totVal -= sub[candi];jurSize--;}Collections.sort(selected);System.out.println("Best jury has value " + (int)((subSum + plusSum) / 2) + " for prosecution and value " + (int)((plusSum - subSum) / 2) + " for defence:");for(int i = 0; i < selected.size(); i++){System.out.print(" " + selected.get(i));}System.out.println();System.out.println();}}??