题解 | #购物单#

//背包问题dp[i][j]表示前i个物品，背包重量为j的情况下能够获得的最大价值
//所以dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])

//dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i][k]]+v[i][k])
import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int money = sc.nextInt();
        int n = sc.nextInt();
        if(n <= 0 || money <= 0){
            System.out.println(0);
        }
        //维度为5 分别表示 价值，重要程度，主件or附件，附件1，附件2
        int[][] goods = new int[n+1][5];
        for(int i=1;i<=n;i++){
            goods[i][0] = sc.nextInt();
            goods[i][1] = sc.nextInt();
            goods[i][2] = sc.nextInt();
            if(goods[i][2]>0){
                if(goods[goods[i][2]][3] == 0){
                    goods[goods[i][2]][3] = i;
                }else{
                    goods[goods[i][2]][4] = i;
                }
            }
        }
        //dp[i][j]表示前i件
        int[][] dp = new int[n+1][money+1];
        for(int i = 1; i <= n; i++){
            int v = 0, v1 = 0, v2 = 0, v3 = 0;
            int tempdp = 0, tempdp1 = 0, tempdp2 = 0, tempdp3 = 0;
            v = goods[i][0];
            tempdp = goods[i][0] * goods[i][1]; //只有当前商品
            if(goods[i][3] !=0 ){ //主件+附件1
                v1 = goods[i][0] + goods[goods[i][3]][0];
                tempdp1 = goods[i][0] * goods[i][1] + goods[goods[i][3]][0] * goods[goods[i][3]][1];
            }
            if(goods[i][4] !=0 ){ //主件+附件1
                v2 = goods[i][0] + goods[goods[i][4]][0];
                tempdp2 = goods[i][0] * goods[i][1] + goods[goods[i][4]][0] * goods[goods[i][4]][1];
            }
            if(goods[i][3] !=0 && goods[i][4] !=0 ){ //主件+附件1+附件2
                v3 = goods[i][0] + goods[goods[i][3]][0] + goods[goods[i][4]][0];
                tempdp3 = goods[i][0] * goods[i][1] + goods[goods[i][3]][0] * goods[goods[i][3]][1] + goods[goods[i][4]][0] * goods[goods[i][4]][1];
            }
            for(int j = 1; j <= money; j++){
                if(goods[i][2] > 0){ //表示商品是附件直接跳过
                    dp[i][j] = dp[i-1][j];
                }else{
                    dp[i][j] = dp[i-1][j];
                    if(j >= v && v!=0){
                        dp[i][j] = Math.max(dp[i][j],dp[i-1][j-v] + tempdp);
                    }
                    if(j >= v1 && v1!=0){
                        dp[i][j] = Math.max(dp[i][j],dp[i-1][j-v1] + tempdp1);
                    }
                    if(j >= v2 && v2!=0){
                        dp[i][j] = Math.max(dp[i][j],dp[i-1][j-v2] + tempdp2);
                    }
                    if(j >= v3 && v3!=0){
                        dp[i][j] = Math.max(dp[i][j],dp[i-1][j-v3] + tempdp3);
                    }
                }
            }
        }
        System.out.println(dp[n][money]);
    }
}