题解 | #购物单#

题意在这里不多赘述,只说重点.
很明显这里要使用动态规划的思想来解决,由于每种商品只能买一次,所以本质上还是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 +
                '}';
    }
}