题解 | #购物单#

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int m = sc.nextInt();
        //1.接收数据,创建m商品;
        Goods[] goods = new Goods[m + 1];
        goods[0] = new Goods(0, 0, 0);
        //因为题目的flag,商品编号从1开始,故goods下标也从1开始,故要加1.
        int i = 1;
    while (sc.hasNext()) {
           goods[i++] = new Goods(sc.nextInt(), sc.nextInt(), sc.nextInt());
        }

        //2.根据flag标号,将附件依附在主件上;
        for (int j = 1; j < m + 1; j++) {
            if (goods[j].flag>0){
                if (goods[goods[j].flag].a1 == 0) //若当前主件仍未分配附件则添加该附件为附件1
                    goods[goods[j].flag].setA1(j);
                else if (goods[goods[j].flag].a2 == 0) //每个附件只能被加一次,一个主件最多可添加两个附件
                    goods[goods[j].flag].setA2(j);
            }
        }
     /*   for (Goods good : goods) {
            if(good.flag==0)
            System.out.println(good);
        }*/

        //对dp数组初始化 :dp[k][j]定义:手中有j元时,任买前0-i中的几件物品达到的最大满意度
        int[][] dp = new int[m + 1][N + 1]; //因为商品价格都是10的倍数,所以这里总钱数也可考虑成10的倍数.3600/10=360,0-359;故加1
        //不用考虑个位数非0,多出的个位数啥也买不起.对是否买得起不影响
        //当有0元时,啥也买不到,故所有j=0时dp为0;
        //对于k=0时0号商品价格和重要度都为0,默认0号为主件,故dp也为0;

        for (int k = 1; k < m + 1; k++) { //其实只用算购买主件的几种情况,附件和主件依附着卖.
            int price  = 0, price1  = 0, price2  = 0, price3  = 0;
            int weight = 0, weight1 = 0, weight2 = 0, weight3 = 0;
            //只买主件
            price = goods[k].price;
            weight = goods[k].weight * price;
            //主件+附件1
            if (goods[k].a1 > 0) {
                price1 = goods[goods[k].a1].price + price;
                weight1 = goods[goods[k].a1].weight * goods[goods[k].a1].price + weight;
            }
            //主件+附件2
            if (goods[k].a2 > 0) {
                price2 = goods[goods[k].a2].price + price;
                weight2 = goods[goods[k].a2].weight * goods[goods[k].a2].price + weight;
            }
            //主件+附件1,2
            if (goods[k].a1 > 0 && goods[k].a2 > 0) {
                price3 = goods[goods[k].a1].price + goods[goods[k].a2].price + price;
                weight3 = goods[goods[k].a1].weight * goods[goods[k].a1].price + goods[goods[k].a2].weight * goods[goods[k].a2].price + weight;
            }

            for (int j = 1; j <= N ; j++) {
                if (goods[k].flag > 0) dp[k][j] = dp[k - 1][j]; //当该物品为附件时不买,
                else {
                    dp[k][j] = dp[k - 1][j]; //问题出现在这儿,如果不直接赋给dp[k][j],而是在4个if里用dp[k-1][j]判断会出现有一个用例出错
                    //这样可以直接在5种情况中选出最大的;
                    if (j  >= price &&price  != 0) //price初始化时为0,肯定j>=price
                        dp[k][j] = Math.max(dp[k][j], dp[k - 1][j-price ] + weight );
                    if (j  >= price1&&price1 != 0)
                        dp[k][j] = Math.max(dp[k][j], dp[k - 1][j-price1] + weight1);
                    if (j  >= price2&&price2 != 0)
                        dp[k][j] = Math.max(dp[k][j], dp[k - 1][j-price2] + weight2);
                    if (j  >= price3&&price3 != 0)
                        dp[k][j] = Math.max(dp[k][j], dp[k - 1][j-price3] + weight3);
                    /*
                    *   错误代码,这里4个if之间没有进行比较,并且缺少和不买i时的比较,
                    *  因为就算主件有附件,也可以连主件都不买
                    * 故在该物品为主件时应当有5种情况:
                    * 1、不买;2、只买主件;3、买主件加附件1;4、买主件加附件2;5、买主件加附件1和附件2
                    * 在以上几种情况中选择最大的。
                    * eg:当买主件加附件1时，用dp[k-1][j-price1],j-price1是指当钱减去主件和附件1时的总钱数
                    * 这时如果买，则刚好够买。
                    *  if (j  >= price &&price  != 0) //price初始化时为0,肯定j>=price
                        dp[k][j] = Math.max(dp[k-1][j], dp[k - 1][j-price ] + weight );
                    if (j  >= price1&&price1 != 0)
                        dp[k][j] = Math.max(dp[k-1][j], dp[k - 1][j-price1] + weight1);
                    if (j  >= price2&&price2 != 0)
                        dp[k][j] = Math.max(dp[k-1][j], dp[k - 1][j-price2] + weight2);
                    if (j  >= price3&&price3 != 0)
                        dp[k][j] = Math.max(dp[k-1][j], dp[k - 1][j-price3] + weight3);
                    * */
                }
            }
        }
        System.out.println(dp[m][N]);
    }
}

class Goods {
    int price;//价格
    int weight;//重要度
    int flag;//是否为附件
    int a1 = 0, a2 = 0; //附件编号,为0说明没有附件

    public Goods(int price, int weight, int flag) {
        this.price = price;
        this.weight = weight;
        this.flag = flag;
    }

    @Override
    public String toString() {
        return "Goods{" +
                "price=" + price +
                ", weight=" + weight +
                ", flag=" + flag +
                ", a1=" + a1 +
                ", a2=" + a2 +
                '}';
    }

    public void setA1(int a1) {
        this.a1 = a1;
    }

    public void setA2(int a2) {
        this.a2 = a2;
    }
}