题解 | #购物单#

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int money = sc.nextInt();
        int m = sc.nextInt();
        /**
            本质上依然属于0/1背包问题，每个商品都有拿与不拿的选项，在有限资源下获取最大的收益
            不同点在于物品分主次，必须整理出附件与主件的关系
         */
        if(money<=0||m<=0) System.out.println(0);
        Good[] goods=new Good[m+1];
        for(int i=1;i<=m;i++){
            int v=sc.nextInt();
            int p=sc.nextInt();
            int q=sc.nextInt();
            if(goods[i]==null){
                goods[i]=new Good(v,p,q);
            }else{
                goods[i].v=v;
                goods[i].p=p;
                goods[i].q=q;
            }
            
            if(q>0){
                if(goods[q]==null){
                    goods[q]=new Good(i);
                }else{
                    if(goods[q].a1==0){
                        goods[q].setA1(i);
                    }else{
                        goods[q].setA2(i);
                    }
                }
                
            }
        }

        int[] dp=new int[money+1];
        for(int i=1;i<=m;i++){
            for(int j=money;j>=1;j--){
                
                int v1=goods[i].getValue();
                int v2=0;
                int v3=0;
                int v4=0;
                
                if(goods[i].a1>0){
                    v2=v1+goods[goods[i].a1].getValue();
                }

                if(goods[i].a2>0){
                    v3=v1+goods[goods[i].a2].getValue();
                }

                if(goods[i].a2>0){
                    v4=v2+goods[goods[i].a2].getValue();
                }

                if(goods[i].q==0){
                    int p1=goods[i].v;
                    if(j>=p1)dp[j]=Math.max(dp[j-p1]+v1,dp[j]);
                    

                    if(v2>0){
                        int p2=goods[i].v+goods[goods[i].a1].v;
                        if(j>=p2)dp[j]=Math.max(dp[j-p2]+v2,dp[j]);
                    }

                    if(v3>0){
                        int p3=goods[i].v+goods[goods[i].a2].v;
                        if(j>=p3)dp[j]=Math.max(dp[j-p3]+v3,dp[j]);
                    }

                    if(v4>0){
                        int p4=goods[i].v+goods[goods[i].a1].v+goods[goods[i].a2].v;
                        if(j>=p4)dp[j]=Math.max(dp[j-p4]+v4,dp[j]);
                    }
                    
                }
            }
        }
        System.out.println(dp[money]);

    }

    private static class Good{
        public int v;
        public int p;
        public int q;

        public int a1=0;
        public int a2=0;

        public Good(int a1){
            this.a1=a1;
        }


        public Good(int v,int p,int q){
            this.v=v;
            this.p=p;
            this.q=q;
        }

        public int getValue(){
            return this.v*this.p;
        }

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

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

        @Override
        public String toString(){
            return "v:"+this.v+",p:"+this.p+",q:"+this.q+",a1:"+this.a1+",a2:"+this.a2;
        } 
    }

}

学习完dp联系一下，使用滚动数组减小空间