题解 | 购物单

import java.util.Scanner;

public class Main{

	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int totalMoney = sc.nextInt()/10;
		int n = sc.nextInt();	
		int[][] prices = new int[n+1][3];
		int[][] values = new int[n+1][3];
		for (int i = 1; i <= n; i++) {
			int a = sc.nextInt()/10;
			int b = sc.nextInt();
			int c = sc.nextInt();
			if (c == 0) {
				prices[i][0] = a;
				values[i][0] = b;
			} else if (prices[c][1] == 0) {
				prices[c][1] = a;
				values[c][1] = b;
			} else {
				prices[c][2] = a;
				values[c][2] = b;
			}
		}

		int[][] dp = new int[n+1][totalMoney+1];
		for (int i = 1; i <= n; i++ ) {
			for (int j = 1; j <= totalMoney; j++) {
				int a = prices[i][0], b = values[i][0];
				int c = prices[i][1], d = values[i][1];
				int e = prices[i][2], f = values[i][2];
				dp[i][j] = j >= a ? Math.max(dp[i-1][j], dp[i-1][j-a] + a*b) : dp[i-1][j];
				dp[i][j] = j >= a + c ? Math.max(dp[i][j], dp[i-1][j-a-c] + a*b + c*d) : dp[i][j];
				dp[i][j] = j >= a + e ? Math.max(dp[i][j], dp[i-1][j-a-e] + a*b + e*f) : dp[i][j];
				dp[i][j] = j >= a + c + e ? Math.max(dp[i][j], dp[i-1][j-a-c-e] + a*b + c*d + e*f) : dp[i][j];
			}
		}
		System.out.println(dp[n][totalMoney]*10);
	}

}

一直没人发，我发一个吧，就是按照大佬们的思路java写了一遍