题解 | #购物单#

动态规划 Java解法

注意点：

1. 内层遍历是从n到1，不是从1到n（还没有完全理解）
2. price和value的第一层数组下标要从1开始，不能从0开始。因为附件中的主件序号是从1开始的

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int N = in.nextInt(); //money
		int m = in.nextInt(); //number, want to buy
		int[][] price = new int[m+1][3];
		int[][] value = new int[m+1][3];
		for(int i=1;i<=m;i++) {
			int v = in.nextInt();
			int p = in.nextInt();
			int q = in.nextInt();
			if(q==0) { //只有主件
				price[i][0] = v/10;
				value[i][0] = v/10*p;
			}else if(price[q][1]==0) { //附件1
				price[q][1] = v/10;
				value[q][1] = v/10*p;
			}else { //附件2
				price[q][2] = v/10;
				value[q][2] = v/10*p;
			}
		}
		int[] dp = new int[N/10+1];
		for(int i=1;i<=m;i++) {
			for(int j=N/10;j>=0;j--) {
				if(price[i][0]<=j) { //加了一个主件还小于钱数
					dp[j] = Math.max(dp[j], value[i][0]+dp[j-price[i][0]]);
				}
				if(price[i][1]!=0 && price[i][0]+price[i][1]<=j) { //主件+附件1后还小于钱数
					dp[j] = Math.max(dp[j], value[i][0]+value[i][1]+dp[j-price[i][0]-price[i][1]]);
				}
				if(price[i][2]!=0 && price[i][0]+price[i][2]<=j) { //主件+附件2后还小于钱数
					dp[j] = Math.max(dp[j], value[i][0]+value[i][2]+dp[j-price[i][0]-price[i][2]]);
				}
				if(price[i][2]!=0 && price[i][0]+price[i][1]+price[i][2]<=j) { //主件+附件1+附件2后还小于钱数
					dp[j] = Math.max(dp[j], value[i][0]+value[i][1]+value[i][2]+dp[j-price[i][0]-price[i][1]-price[i][2]]);
				}
			}
		}
		System.out.println(dp[N/10]*10);
		in.close();
	}
}