题解 | #购物单#

##1.这是一个背包问题的变体； ##2.明确购物规则： 只能在购买主件的前提下购买附件，因此将物品分为两类，主件类和从属类； ##3.状态dp[i][value]表示当前第i个主件的能获得的最大期望值； ##4.选择(遍历所有主件)：不购买主件i，购买主件i(0附件），购买主件i+任一附件，购买主件i+两个附件

import java.util.*;

public class Main{
    public static void main(String[] args){
      //输入
        Scanner in=new Scanner(System.in);
      //总金额
      	int money=in.nextInt();
      //物件数
      	int num=in.nextInt();
      //记录主件的附件 addition[i][0]表示主件i的第一个附件
      	int[][] addtion=new int[num+1][num+1];
       //价格和权重
      	int[] w=new int[num+1];
        int[] v=new int[num+1];
      //记录主件
        ArrayList<Integer> major=new ArrayList<>();
      //从1开始
        major.add(0);
        for(int i=1;i<=num;i++){
            int a=in.nextInt();
            int b=in.nextInt();
            int c=in.nextInt();
            v[i]=a/10;w[i]=b;
            if(c!=0){
                int index=0;
                while(addtion[c][index]!=0)
                    index++;
                addtion[c][index]=i;
            }else{
                major.add(i);
            }
        }
      //除以10是因为金额太大了+金额都是10 的倍数
        int[][] dp=new int[major.size()][money/10+1];
      //遍历主件
        for(int i=1;i<major.size();i++){
            int index=major.get(i);
            for(int value=1;value<=money/10;value++){
        //开始选择
                dp[i][value]=dp[i-1][value];
                if(value>=v[index])
                    dp[i][value]=Math.max(dp[i-1][value], dp[i-1][value-v[index]]+v[index]*w[index]);
                if(addtion[index][0]!=0&&value>=v[index]+v[addtion[index][0]])
                    dp[i][value]=Math.max(dp[i][value],dp[i-1][value-v[index]-v[addtion[index][0]]]+
                    v[index]*w[index]+v[addtion[index][0]]*w[addtion[index][0]]);
                if(addtion[index][1]!=0&&value>=v[index]+v[addtion[index][1]])
                    dp[i][value]=Math.max(dp[i][value],dp[i-1][value-v[index]-v[addtion[index][1]]]+
                    v[index]*w[index]+v[addtion[index][1]]*w[addtion[index][1]]);
                if(addtion[index][0]!=0&&addtion[index][1]!=0&&value>=v[index]+v[addtion[index][0]]+v[addtion[index][1]])
                    dp[i][value]=Math.max(dp[i][value],dp[i-1][value-v[index]-v[addtion[index][0]]-v[addtion[index][1]]]+v[index]*w[index]+v[addtion[index][1]]*w[addtion[index][1]]+v[addtion[index][0]]*w[addtion[index][0]]);
            }
        }
      //输出结果
        System.out.println(dp[major.size()-1][money/10]*10);
    }
}