转化为分组背包问题

解题思路:

注意事项:

参考代码:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.ArrayList;

public class Main {
    static StreamTokenizer cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    static int month[] = new int[] { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
    static int n, m, k;
    static int fen[][] = new int[400][1010];//把票据分组,由于不是闰年,那么可知一共有365天,即分成365组
    static int f[][] = new int[400][5010];//表示前i天中选,是否存在报销价格为j的方案,1表示存在,0表示不存在
    static int st[] =new int[5010];//标记记录报销金额为j时,最先在哪一天出现
    static int len[] = new int[400];//记录365个分组,，每个分组有多少张票据
    static int sum(int x) {//
        int res = 0;
        for (int i = 1; i <= x; i++) {
            res += month[i];
        }
        return res;
    }
    static int nextInt() throws IOException {
        cin.nextToken();
        return (int) cin.nval;
    }
    public static void main(String[] args) throws IOException {
        n = nextInt();
        m = nextInt();
        k = nextInt();
        int a, b, c;
        for (int i = 1; i <= n; i++) {
            a = nextInt();
            b = nextInt();
            c = nextInt();
            int idx = sum(a - 1) + b;//把月份+天数转化为365天格式的编号
            fen[idx][++len[idx]] = c;
            f[idx][c]=1;
        }
        f[0][0]=1;
        for(int i=0;i<5010;i++) st[i]=1000000;
        int maxv = 0;
        st[0]=0;
        for (int i = 1; i <=365; i++) {//枚举分组
            for (int t = 1; t <= len[i]; t++) {//枚举该分组的票据
                int x = fen[i][t];//x表示当前票据的报销金额
                for (int j = m; j >= 0; j--) {
                    if (j >= x&&st[j-x]<=Math.max(0,i-k)) {//如果st[j-x]最早出现的位置小于等于i-k天,那么j就是合法的
                        f[i][j]=1;
                    }
                    if (f[i][j] > 0) {
                        st[j]=Math.min(st[j], i);
                        maxv = Math.max(maxv, j);
                       }
                }
            }
        }
        System.out.println(maxv);
    }
}