题解 | #购物单#

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()){
            int money = sc.nextInt();
            int nums = sc.nextInt();
            int[][] goodstable = new int[nums][3];
            ArrayList<Goods> goodslistmain = new ArrayList<Goods>(); //定义主件列表
            ArrayList<Goods> goodslistacc = new ArrayList<Goods>(); //定义附件列表
            int vallist[]=new int[nums];//为了找出价格最低的物品(填动态规划表时作为第一列)，将所有价格存在数组中
            //将输入填充到主件列表和附件列表
            for (int i =0;i<nums;i++){
                goodstable[i][0] = sc.nextInt();
                goodstable[i][1] = sc.nextInt();
                goodstable[i][2] = sc.nextInt();
                vallist[i]=goodstable[i][0];
                Goods good = new Goods(goodstable[i],i+1);
                if (goodstable[i][2]==0){
                    goodslistmain.add(good);
                }else if (goodstable[i][2]!=0){
                    goodslistacc.add(good);
                }
            }
            int minval=Arrays.stream(vallist).min().orElse(0);//找出价格最低的那件
            int cols = (money-minval)/10+1; //总列数
            //将每个主件和附件关联起来，便于后续做场景。
            for (int i=0;i<goodslistmain.size();i++){
                Goods maing = goodslistmain.get(i);
                for (int j=0;j<goodslistacc.size();j++){
                    Goods accgood = goodslistacc.get(j);
                    if (maing.code == accgood.q) maing.addaccessory(accgood);
                }
            }

            //开始填动态规划表
            int rows = goodslistmain.size();
            int[][] table = new int[rows+1][cols+1];
            //第一行和第一列都填充为0
            for (int l=0;l<=cols;l++) {table[0][l]=0;}
            for (int h=0;h<=rows;h++) {table[h][0]=0;}
            //从第二行第二列开始填表
            for (int i=1;i<=rows;i++){
                Goods maingood = goodslistmain.get(i-1);
                ArrayList<Integer> subv = new ArrayList<>();
                ArrayList<Integer> subvp = new ArrayList<>();
                //根据附件个数生成每行主件的子场景，将价格和满意度分别存在subv,subvp数组中
                switch (maingood.accnums){
                    case 0:
                        subv.add(maingood.v);//主件价格
                        subvp.add(maingood.v*maingood.p);//主件满意度
                        break;
                    case 1:
                        Goods a0 = maingood.accessorys.get(0);
                        subv.add(maingood.v);//主件价格
                        subvp.add(maingood.v*maingood.p);//主件满意度
                        subv.add(maingood.v+a0.v);//主件+附件1的价格
                        subvp.add(maingood.v*maingood.p+a0.v*a0.p);//主件+附件1的满意度
                        break;
                    case 2:
                        Goods acc1 = maingood.accessorys.get(0);
                        Goods acc2 = maingood.accessorys.get(1);
                        //主件
                        subv.add(maingood.v);
                        subvp.add(maingood.v*maingood.p);
                        //主件+附件1
                        subv.add(maingood.v+acc1.v);
                        subvp.add(maingood.v*maingood.p+acc1.v*acc1.p);
                        //主件+附件2
                        subv.add(maingood.v+acc2.v);
                        subvp.add(maingood.v*maingood.p+acc2.v*acc2.p);
                        //主件+附件1+附件2
                        subv.add(maingood.v+acc1.v+acc2.v);
                        subvp.add(maingood.v*maingood.p+acc1.v*acc1.p+acc2.v*acc2.p);
                        break;
                }
                for (int j=1;j<=cols;j++){
                    int colmoney = minval+(j-1)*10;//从物品清单中价格最小的那个开始填表，以10为步长
                    int[] preval = new int[subv.size()];
                    //遍历每行的子场景，对子场景中的每个值分别判断，找出最大值
                    for (int s=subv.size()-1;s>=0;s--){
                        int colmoneyextra = colmoney-subv.get(s);
                        if (colmoneyextra>=0&&colmoneyextra<minval){//钱够，但不剩余或剩余的已经买不了别的东西了
                            preval[s]=Math.max(subvp.get(s),table[i-1][j]);
                        }else if (colmoneyextra>=minval){//钱够，剩余的还可以买别的东西
                            int k = (colmoneyextra-minval)/10+1;
                            preval[s]=Math.max(subvp.get(s)+table[i-1][k],table[i-1][j]);
                        }else {
                            preval[s] = table[i-1][j];
                        }
                    }
                    table[i][j]=Arrays.stream(preval).max().getAsInt();
                }
            }
            System.out.println(table[rows][cols]);
        }
    }
    //创建商品类及其方法
    public static class Goods{
        int v,p,q;
        int code;
        int accnums=0;
        ArrayList<Goods> accessorys = new ArrayList<Goods>();
        public Goods(int[] goodpro,int c){
            this.v = goodpro[0];
            this.p = goodpro[1];
            this.q = goodpro[2];
            this.code = c;
        }
        public void addaccessory(Goods accessory){
            accessorys.add(accessory);
            accnums +=1;
        }
        public ArrayList<Goods> getAccessorys(){
            return accessorys;
        }

    }
}