题解 | 购物单

import java.util.*;
/*
有依赖的背包问题
附件依赖于主件，其实还是选主件的问题，只是在不选和怎么选之间选择
设dp[i][j]表示前i件物品成本不超过j元时获得的最大满意度
只针对主件，x表示上一个主件的位置,遇到附件之间跳过
1)不选当前主件:dp[i][j]=dp[x][j]
2)只选主件:dp[i][j]=Math.max(第一种情况,dp[x][j-主件价格]+主件满意度)
3)选主件+附件1:dp[i][j]=Math.max(前两种情况,dp[x][j-主件价格-附件1价格]+主件满意度+附件1满意度)
4)选主件+附件2:dp[i][j]=Math.max(前三种情况,dp[x][j-主件价格-附件2价格]+主件满意度+附件2满意度)
5)选主件+附件1+附件2:dp[i][j]=Math.max(前四种情况,dp[x][j-主件价格-附件1价格-附件2价格]+主件满意度+附件1满意度+附件2满意度)
需要二维数组follows[][]存储主件对应的附件位置,方便在操作当前主件时能够找到对应的附件
 */
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        //输入总预算、物品个数
        int n=in.nextInt();
        int m=in.nextInt();
        //输入各个物品的价格、重要度、编号
        int []costs=new int [m];
        int []value=new int [m];
        int []points=new int [m];
        for(int i=0;i<m;i++){
            costs[i]=in.nextInt();
            value[i]=costs[i]*in.nextInt();//直接计算满意度
            points[i]=in.nextInt();
        }
        //follows记录主件的附件位置，初始化为-1
        int [][]follows=new int [m][2];//最多只有两个附件
        for(int []row:follows) Arrays.fill(row,-1); 
        for(int i=0;i<m;i++)
            if(points[i]!=0){
                //先判断第几个附件
                //如果是第一个
                if(follows[points[i]-1][0]==-1) follows[points[i]-1][0]=i;
                else follows[points[i]-1][1]=i;
            }
        //开始背包
        int [][]dp = new int [m+1][n+1];
        dp[0][0]=0;
        int x=0;
        for(int i=1;i<=m;i++){
            //不是主件直接跳过
            if(points[i-1]!=0) continue;
            for(int j=0;j<=n;j++){
                //第一种情况，不选当前主件
                dp[i][j]=dp[x][j];
                //第二种情况，只选主件
                if(j>=costs[i-1])
                    dp[i][j]=Math.max(dp[i][j],dp[x][j-costs[i-1]]+value[i-1]);//与第一种情况比较
                //第三种情况，选主件+附件1(如果有的话)
                if(follows[i-1][0]!=-1 && j>=costs[i-1]+costs[follows[i-1][0]])
                    dp[i][j]=Math.max(dp[i][j],dp[x][j-costs[i-1]-costs[follows[i-1][0]]]+value[i-1]+value[follows[i-1][0]]);//与第二种情况比较
                //第四种情况，选主件+附件2(如果满足条件)
                if(follows[i-1][1]!=-1 && j>=costs[i-1]+costs[follows[i-1][1]])
                    dp[i][j]=Math.max(dp[i][j],dp[x][j-costs[i-1]-costs[follows[i-1][1]]]+value[i-1]+value[follows[i-1][1]]);//与第三种情况比较
                //第五种情况，选主件+附件1+附件2
                if(follows[i-1][0]!=-1 && follows[i-1][1]!=-1 && j>=costs[i-1]+costs[follows[i-1][0]]+costs[follows[i-1][1]])
                    dp[i][j]=Math.max(dp[i][j],dp[x][j-costs[i-1]-costs[follows[i-1][0]]-costs[follows[i-1][1]]]+value[i-1]+value[follows[i-1][0]]+value[follows[i-1][1]]);
            }
            //当前的主件换成上一次的主件
            x=i;
        }
        //最后输出最后一个主件的位置
        System.out.print(dp[x][n]);
    }
}