2017百度之星资格赛：1004. 度度熊的午饭时光

package baidu;
import java.util.*;
public class Main {
    static int B;//预算
    static int N;//菜品数量
    static int[] value = new int[1002];//菜品得分
    static int[] money = new int[1002];//菜品价格
    static int[][] result = new int[101][1002];
    static int[] sta = new int[120];
    static int top = 0,ans = 0;
    static void print(int i,int wt) {
        if(i == 1) {
            if(result[i][wt] != 0) {
                sta[top++] = 1;
                ans += money[1];
            }
            return;
        }
        if(result[i][wt] > result[i - 1][wt]) {
            print(i - 1,wt - money[i]);
            sta[top++] = i;
            ans += money[i];//如果选了，则打印编号
        } 
        else 
            print(i - 1,wt);
    }
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int t = cin.nextInt();
        int sum = 0;
        while((t--) != 0) {
            for(int i = 0;i < 101;i++)
                for(int j = 0;j < 1002;j++)
                    result[i][j] = 0;
            top = ans = 0;
            B = cin.nextInt();
            N = cin.nextInt();
            for(int i = 1;i <= N;i++) {
                value[i] = cin.nextInt();
                money[i] = cin.nextInt();
            }
            for(int i = 1;i <= N;i++) {
                for(int j = 0;j <= B;j++) {
                    if(j < money[i])
                        result[i][j] = result[i - 1][j];
                    else
                        result[i][j] = 
                        Math.max(result[i - 1][j],result[i - 1][j - money[i]] + value[i]);
                }
            }
            if(N != 0)
                print(N,B);
            System.out.println("Case #" + ++sum + ":");
            System.out.print(result[N][B] + " ");
            System.out.println(ans);
            if(0 < top)
                System.out.print(sta[0]);
            for(int i = 1; i < top; ++i)
                    System.out.print(" " +sta[i]);
            if(top > 0)
                System.out.println("");
        }
    }
}