题解 | #购物单#

import java.util.Scanner;
/*

• 物品分为主副件，每个主件可能有附件(最多有两个附件)，买要买附件则必须买起对应的主件，求在资金一定的情况下能够买到的最大贡献度

• 贡献度=价值*重要程度

• 物品goods:

• p:表示物品价值 w:表示贡献度 q:表示该物品是否为主件，若为则q=0,若不为则q表示所对应的主件序号

• dp[m][n]:表示在资金为m的情况下从n个物品中能够买到的最大贡献度

• dp[m][n] = max{不买第n个物品，买第n个物品}

• 当第n个物品为附件时,此时是不能购买该物品的

• dp[m][n] = dp[m][n-1];

• 当第n个物品不为附件时，此时购买该物品时可以购买该物品的附件，因此最多可以分为4种情况

• 情况1：只买主件 情况2：买主件+附件1 情况3：买主件+附件2 情况3：买主件+附件1+附件2

• 情况1：只买主件 = dp[m-goods.p][n-1]+goods.p*goods.w

• 情况2：买主件+附件1 = dp[m-goods.p-goods.附件1.p][n-1] + goods.pgoods.w + goods.附件1.pgoods.附件1.w

• 情况3：买主件+附件1 = dp[m-goods.p-goods.附件2.p][n-1] + goods.pgoods.w + goods.附件2.pgoods.附件2.w

• 情况4：买主件+附件1 = dp[m-goods.p-goods.附件1.p-goods.附件2.p][n-1] +

• goods.pgoods.w + goods.附件1.pgoods.附件1.w +

• goods.附件2.p*goods.附件2.w

• dp[m][n] = max{不买第n个物品，买第n个物品} = max{dp[m][n-1],情况1，情况2，情况3，情况4};

• /
  public class Main {
  public static void main(String[] args) {

    Scanner sc = new Scanner(System.in);
    //输入资金
    int m = sc.nextInt();
    //输入物品总数
    int n = sc.nextInt();
    //输入物品信息
    goods[] goods = new goods[n+1];
    for (int i = 1; i <= n; i++) {
        int p = sc.nextInt();
        int w = sc.nextInt();
        int q = sc.nextInt();
        //构造商品
        goods[i] = new goods(p, w, q);
        if (q!=0) {//表明第i个物品是第q个物品的附属品
            if (goods[q].add1==0) {
                goods[q].add1 = i;
            }else{
                goods[q].add2 = i;
            }
        }
    }
    System.out.println(calue(m,n,goods));

  }

  private static int calue(int m, int n, goods[] goods) {

    int[][] dp = new int[m+1][n+1];
    for (int i = 1; i <= m; i++) {//表示金钱
        for (int j = 1; j <= n ; j++) {//表示物品
            //判断第j件物品是否为主件
            if (goods[j].q==0) {//为主件
                int p1 = 0,p2 = 0,p3 = 0,p4 = 0;
                int v1 = 0,v2 = 0,v3 = 0,v4 = 0;
                //情况1：只买主件
                p1 = goods[j].p; //价格
                v1 = goods[j].p*goods[j].w; //贡献
                //情况2：买主件+附件1
                if (goods[j].add1!=0) {
                    p2 = goods[j].p + goods[goods[j].add1].p;
                    v2 = goods[j].p*goods[j].w + goods[goods[j].add1].p*goods[goods[j].add1].w;
                }
                //情况3：买主件+附件2
                if (goods[j].add2!=0) {
                    p3 = goods[j].p + goods[goods[j].add2].p;
                    v3 = goods[j].p*goods[j].w + goods[goods[j].add2].p*goods[goods[j].add2].w;
                }
                //情况4：买主件+附件1+附件2
                if (goods[j].add1!=0 && goods[j].add2!=0) {
                    p4 = p2+p3-p1;
                    v4 = v2+v3-v1;
                }
                dp[i][j] = dp[i][j-1];
                if (p1<=i) {
                    dp[i][j] = Math.max(dp[i][j], dp[i-p1][j-1]+v1);
                }
                if(p2<=i && p2!=0){
                    dp[i][j] = Math.max(dp[i][j], dp[i-p2][j-1]+v2);
                }
                if(p3<=i && p3!=0){
                    dp[i][j] = Math.max(dp[i][j], dp[i-p3][j-1]+v3);
                }
                if(p4<=i && p4!=0){
                    dp[i][j] = Math.max(dp[i][j], dp[i-p4][j-1]+v4);
                }
            }else{//为附件
                dp[i][j] = dp[i][j-1];
            }
        }
    }
    return dp[m][n];

  }
  }
  class goods{
  int p;
  int w;
  int q;
  int add1 = 0;//表示附件1的序号
  int add2 = 0;//表示附件2的序号
  public goods(int p, int w, int q) {

    this.p = p;
    this.w = w;
    this.q = q;

  }
  }