金明的预算方案-JAVA（动态规划）

import java.util.Scanner;

public class Main {
	public static void main(String[] ages)

	{
		Scanner scanner = new Scanner(System.in);
		int n=scanner.nextInt();
		int m=scanner.nextInt();
		int [] v=new int [m+1];
		int [] p=new int [m+1];
		int [] q=new int [m+1];
		int [][]dp=new int [m+1][n+1];
		for (int i = 1; i <= m; i++) {
			v[i]=scanner.nextInt();//价格
			p[i]=scanner.nextInt();//重要度
			q[i]=scanner.nextInt();//附件
			p[i]*=v[i];//价格*重要度
			//是否是附件
			if (q[i]!=0) {
				p[i]+=p[q[i]];//当前附件的乘积加上主件的乘积
				v[i]+=v[q[i]];//加上主件的价值
			}
		}
		//01背包
		for (int i = 1; i <= m; i++) {
			for (int j = 1; j j) {
					dp[i][j]=dp[i-1][j];
				}
				else {
					dp[i][j]=Math.max(dp[i-1][j], dp[i-1][j-v[i]]+p[i]);
				}
			}
		}
		System.out.println(dp[m][n]);
	}
}