题意在这里不多赘述,只说重点.很明显这里要使用动态规划的思想来解决,由于每种商品只能买一次,所以本质上还是01背包问题.但是和01背包不同的是,商品被分成了主件和附件,并且,附件是当可以买主件时,才能购买,所以很明显,附件的存在是为了作为主件的某一种情况,当可以购买主件时,也就是j>=priceOfLeader时, j-priceOfLeader能否再买附件,如果可以买,是不买的满意度大还是买的满意度大,是买一件还是两件,只能买一件的话,是买附件一还是附件2.代码如下:import java.util.Scanner;public class Demo4 {    public static void main(String[] args) {        Scanner in = new Scanner(System.in);        int n = 0;        int m = 0;        if(in.hasNextInt()){            n = in.nextInt();            m = in.nextInt();        }        Good[] goods = new Good[m+1];        for (int i = 1; i <= m; i++) {            goods[i] = new Good();        }        for (int i = 1; i <= m; i++) {            if (in.hasNextInt()){                int v = in.nextInt();                int p = in.nextInt();                int q = in.nextInt();                goods[i].price = v;                goods[i].improtant = p;                if (q == 0){                    //说明编号为i的good是leader                    goods[i].isLeader = true;                }else{                    //说明编号为i的good是编号为q的good的follower                    if (goods[q].follower1 == 0){                        goods[q].follower1 = i;                    }else{                        goods[q].follower2 = i;                    }                }            }        }        int[][] dp = new int[m+1][n+1];        for (int i = 1; i<= m ; i++){            for (int j = 1; j <= n ; j++){                dp[i][j] = dp[i - 1][j];                if (!goods[i].isLeader) {                    continue;                }                if (j >= goods[i].price){                    dp[i][j] = Math.max(dp[i - 1][j], dp[i-1][j-goods[i].price]+goods[i].price*goods[i].improtant);                }                if (goods[i].follower1 != 0 && j >= (goods[i].price+goods[goods[i].follower1].price)){                    int s1 = dp[i-1][j-goods[i].price]+goods[i].price*goods[i].improtant;                    int s2 = dp[i-1][j-goods[i].price-goods[goods[i].follower1].price]+goods[i].price*goods[i].improtant+goods[goods[i].follower1].price*goods[goods[i].follower1].improtant;                    int maxS = Math.max(s1,s2);                    dp[i][j] = Math.max(dp[i - 1][j], maxS);                }                if (goods[i].follower2 != 0 && j >= (goods[i].price+goods[goods[i].follower2].price)){                    int s1 = dp[i-1][j-goods[i].price]+goods[i].price*goods[i].improtant;                    int s3 = dp[i-1][j-goods[i].price-goods[goods[i].follower2].price]+goods[i].price*goods[i].improtant+goods[goods[i].follower2].price*goods[goods[i].follower2].improtant;                    int maxS = Math.max(s1,s3);                    dp[i][j] = Math.max(dp[i - 1][j], maxS);                }                if (goods[i].follower1 != 0 && goods[i].follower2 != 0 && j >= (goods[i].price+goods[goods[i].follower1].price) && j >= (goods[i].price+goods[goods[i].follower2].price)){                    //判断三种情况的满意度                    int s1 = dp[i-1][j-goods[i].price]+goods[i].price*goods[i].improtant;                    int s2 = dp[i-1][j-goods[i].price-goods[goods[i].follower1].price]+goods[i].price*goods[i].improtant+goods[goods[i].follower1].price*goods[goods[i].follower1].improtant;                    int s3 = dp[i-1][j-goods[i].price-goods[goods[i].follower2].price]+goods[i].price*goods[i].improtant+goods[goods[i].follower2].price*goods[goods[i].follower2].improtant;                    int maxS = Math.max(Math.max(s1,s2),s3);                    dp[i][j] = Math.max(dp[i - 1][j], maxS);                }                if (goods[i].follower1 != 0 && goods[i].follower2 != 0 && j >= (goods[i].price+goods[goods[i].follower2].price+goods[goods[i].follower1].price)){                    int s1 = dp[i-1][j-goods[i].price]+goods[i].price*goods[i].improtant;                    int s2 = dp[i-1][j-goods[i].price-goods[goods[i].follower1].price]+goods[i].price*goods[i].improtant+goods[goods[i].follower1].price*goods[goods[i].follower1].improtant;                    int s3 = dp[i-1][j-goods[i].price-goods[goods[i].follower2].price]+goods[i].price*goods[i].improtant+goods[goods[i].follower2].price*goods[goods[i].follower2].improtant;                    int s4 = dp[i-1][j-goods[i].price-goods[goods[i].follower1].price-goods[goods[i].follower2].price]+goods[i].price*goods[i].improtant+goods[goods[i].follower1].price*goods[goods[i].follower1].improtant+goods[goods[i].follower2].price*goods[goods[i].follower2].improtant;                    int maxS = Math.max(Math.max(s1,s2),Math.max(s3,s4));                    dp[i][j] = Math.max(dp[i - 1][j], maxS);                }            }        }        System.out.println(dp[m][n]);    }}class Good{    public int price;    public int improtant;    public boolean isLeader = false;    public int follower1 = 0;    public int follower2 = 0;    @Override    public String toString() {        return "Good{" +                "price=" + price +                ", improtant=" + improtant +                ", isLeader=" + isLeader +                ", follower1=" + follower1 +                ", follower2=" + follower2 +                '}';    }}