题解 | #购物单#

Java 构建物品类

类似0-1背包问题

我这里将附物品看作可以改变主物品价值和价格的一个物品，也就是一个主物品拥有多组价值和价格

public class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        //价值 = 重要度 * 价格
        //int数组中为价值/价格
        List<int[][]> list = new ArrayList<>();
        //主物品的id list
        List<Integer> idList = new ArrayList<>();
        //所有物品的主键和Good
        Map<Integer,Good> goodMap = new LinkedHashMap<>();
        int N,m;
        N = in.nextInt();
        m = in.nextInt();
        for(int i = 0; i < m; i++){
            int v,p,q;//价格，重要度，主附件
            v = in.nextInt();
            p = in.nextInt();
            q = in.nextInt();
            if(q == 0){
                idList.add(i + 1);
            }
            Good good = new Good(i + 1,v,p,q);
            goodMap.put(i + 1,good);
        }
        goodMap.forEach((k,v) ->{
            int q = v.getQ();
            if(q != 0){
                int idF = v.getId();
                if(goodMap.get(q).getId1() == 0){
                    goodMap.get(q).setId1(idF);
                }else if(goodMap.get(q).getId2() == 0){
                    goodMap.get(q).setId2(idF);
                }
            }
        });
        /*
        for(int i = 0; i < m; i++){
            int v,p,q;//价格，重要度，主附件
            v = in.nextInt();
            p = in.nextInt();
            q = in.nextInt();
            if(q == 0){
                int[][] arr = new int[4][2];
                arr[0][0] = v * p;
                arr[0][1] = v;
                list.add(arr);
            }
            else{
                int[][] arr = list.get(q - 1);
                if(arr[1][0] == 0){
                    arr[1][0] = arr[0][0] + v * p;
                    arr[1][1] = arr[0][1] + v;
                }else{
                    arr[2][0] = arr[0][0] + v * p;
                    arr[2][1] = arr[0][1] + v;
                    arr[3][0] = arr[1][0] + v * p;
                    arr[3][1] = arr[1][1] + v;
                }
                list.remove(q - 1);
                list.add(q - 1,arr);
            }
        }*/
        int nums = idList.size();
        int[][] dp = new int[nums][N + 1];
        idList.forEach(v ->{
            int[][] arr = new int[4][2];
            Good good = goodMap.get(v);
            arr[0][0] = good.getV() * good.getP();
            arr[0][1] = good.getV();
            if(good.getId1() != 0){
                Good good1 = goodMap.get(good.getId1());
                arr[1][0] = arr[0][0] + good1.getV() * good1.getP();
                arr[1][1] = arr[0][1] + good1.getV();
            }
            if(good.getId2() != 0){
                Good good2 = goodMap.get(good.getId2());
                arr[2][0] = arr[0][0] + good2.getV() * good2.getP();
                arr[2][1] = arr[0][1] + good2.getV();
                arr[3][0] = arr[1][0] + good2.getV() * good2.getP();
                arr[3][1] = arr[1][1] + good2.getV();
            }
            list.add(arr);
        });
        for(int j = 0; j <= N; j++){
            int max = 0;
            int[][] arr = list.get(0);
            for(int k = 0; k < 4; k++){
                if((j - arr[k][1]) >= 0){
                    max = Math.max(max,arr[k][0]);
                }
            }
            dp[0][j] = max;
        }
        for(int i = 0; i < nums; i++){
            dp[i][0] = 0;
        }
        for(int i = 1; i < nums; i++){
            for(int j = 1; j <= N; j++){
                int max = dp[i-1][j];
                int[][] arr = list.get(i);
                for(int k = 0; k < 4; k++){
                    if((j - arr[k][1]) >= 0){
                        max = Math.max(max,dp[i-1][j - arr[k][1]] + arr[k][0]);
                    }
                }
                dp[i][j] = max;
            }
        }
        System.out.println(dp[nums-1][N]);
    }
}

class Good{
    /**
    * id
    */
    private int id;
    /**
    * 价格
    */
    private int v;
    /**
    * 重要度
    */
    private int p;
    /**
    * 所属主键编号
    */
    private int q;
    /**
    * 附件1 id
    */
    private int id1;
    /**
    * 附件2 id
    */
    private int id2;
    
    public Good(int id,int v,int p,int q){
        this.id = id;
        this.v = v;
        this.p = p;
        this.q = q;
    }
    public int getId(){
        return id;
    }
    public int getV(){
        return v;
    }
    public int getP(){
        return p;
    }
    public int getQ(){
        return q;
    }
    public void setId1(int id1){
        this.id1 = id1;
    }
    public int getId1(){
        return id1;
    }
    public void setId2(int id2){
        this.id2 = id2;
    }
    public int getId2(){
        return id2;
    }
}