题意整理。

• 给定一堆物品，物品分为主件和附件，每件物品都有一个重要度以及一个价格，想买某个附件，必须先买对应的主件。
• 现在王强有N元的本金，问他在不超出预算的情况下，怎么购买物品，才能使得所买物品的价格与重要度之积的累加和最大。

方法一（动态规划）

1.解题思路

本题实际上是一个01背包问题，背包的容量是N元的预算，目标价值即是物品的价格与重要度之积的累加和。难点在于主件和附件的设定，所以在进行动态规划之前，需要先进行预处理，区分出主件和附件，然后动态规划部分，根据预处理的结果分情况进行处理。

• 状态定义:$dp[i][j]dp[i][j]$表示总钱数为j，物品个数为i时价格与重要度之积的累加和最大值。
• 状态转移:首先默认不选当前物品，即$dp[i][j]=dp[i-1][j]dp[i][j]=dp[i-1][j]$,然后考虑只有主件的情况，即$dp[i][j]=Math\mathrm{.}max(dp[i][j],dp[i-1][j-price[i][0]]+value[i][0])dp[i][j]=Math.max(dp[i][j],dp[i-1][j-price[i][0]]+value[i][0])$，然后考虑主件和附件1的情况，即$dp[i][j]=Math\mathrm{.}max(dp[i][j],dp[i-1][j-price[i][0]-price[i][1]]+value[i][0]+value[i][1])dp[i][j]=Math.max(dp[i][j],dp[i-1][j-price[i][0]-price[i][1]]+value[i][0]+value[i][1])$，然后考虑主件和附件2的情况，即$dp[i][j]=Math\mathrm{.}max(dp[i][j],dp[i-1][j-price[i][0]-price[i][2]]+value[i][0]+value[i][2])dp[i][j]=Math.max(dp[i][j],dp[i-1][j-price[i][0]-price[i][2]]+value[i][0]+value[i][2])$，然后考虑主件和两个附件的情况，即$dp[i][j]=Math\mathrm{.}max(dp[i][j],dp[i-1][j-price[i][0]-price[i][1]-price[i][2]]+value[i][0]+value[i][1]+value[i][2])dp[i][j]=Math.max(dp[i][j],dp[i-1][j-price[i][0]-price[i][1]-price[i][2]]+value[i][0]+value[i][1]+value[i][2])$。

举例说明：

比如输入：
	1000 5
	800 2 0
	400 5 1
	300 5 1
	400 3 0
	500 2 0
对于物品1，价格为800，可以跟新800到1000的所有状态；对于物品2，为物品1的附件1，1200
大于1000，直接跳过；对于物品3，为物品1的附件2，1300大于1000，直接跳过；然后考虑物品
1与两个附件的情况，1500大于1000，直接跳过；对于物品4，价格为400，可以跟新400到1000
的所有状态；对于物品5，价格为500，可以跟新500到1000的所有状态；

图解展示：

2.代码实现

import java.util.Scanner;

public class Main {    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);        
        int N = scanner.nextInt();    // 总钱数       
        int m = scanner.nextInt();    // 购买物品个数或物品id
        int[][] dp=new int[m+1][N+1];
        // 分组，0为主件，1为附件1，2为附件2
        int[][] price=new int[60][3];    // 物品价格
        int[][] value=new int[60][3];    // 物品价值
        for(int i=1;i<=m;i++){
            int p=scanner.nextInt();
            int v=scanner.nextInt();
            int q=scanner.nextInt();
            if(q==0){
                price[i][0]=p;
                value[i][0]=p*v;
            }
            //注意q为主件id对应的附件，price[q][1]为0,则默认选主件q对应的附件1
            else if(price[q][1]==0){
                price[q][1]=p;
                value[q][1]=p*v;
            }
            //如果附件1已经有了，则作为附件2
            else{
                price[q][2]=p;
                value[q][2]=p*v;
            }             
        }
        for(int i=1;i<=m;i++){
            for(int j=0;j<=N;j++){
                //默认不选当前物品
                dp[i][j]=dp[i-1][j];
                if(price[i][0]==0) continue;
                //主件的情况
                if(j>=price[i][0]){
                    dp[i][j]=Math.max(dp[i][j],dp[i-1][j-price[i][0]]+value[i][0]);
                }
                //主件和附件1的情况
                if(price[i][1]!=0&&j>=price[i][0]+price[i][1]){                   
                    dp[i][j]=Math.max(dp[i][j],dp[i-1][j-price[i][0]-price[i][1]]+value[i][0]+value[i][1]);                   
                }
                //主件和附件2的情况
                if(price[i][2]!=0&&j>=price[i][0]+price[i][2]){                   
                    dp[i][j]=Math.max(dp[i][j],dp[i-1][j-price[i][0]-price[i][2]]+value[i][0]+value[i][2]);                   
                }
                //主件和两个附件的情况
                if(price[i][1]!=0&&price[i][2]!=0&&j>=price[i][0]+price[i][1]+price[i][2]){
                    dp[i][j]=Math.max(dp[i][j],dp[i-1][j-price[i][0]-price[i][1]-price[i][2]]+value[i][0]+value[i][1]+value[i][2]);                    
                }
            }
        }
        System.out.println(dp[m][N]);
    }   
}

3.复杂度分析

• 时间复杂度：两层循环，最多执行$m\ast (N+1)m*(N+1)$次，所以时间复杂度为$O(m\ast N)O(m*N)$。
• 空间复杂度：需要额外大小为$(m+1)\ast (N+1)(m+1)*(N+1)$的dp数组，所以空间复杂度为$O(m\ast N)O(m*N)$。

方法二（空间压缩）

1.解题思路

由于状态转移的过程中，每次状态的跟新只与前一轮的状态有关，所以可以利用逆序循环，将维度减小一层。逆序循环，是为了避免前面的状态被重复计算，因为每件物品只能选一次。

2.代码实现

import java.util.Scanner;

public class Main {    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);        
        int N = scanner.nextInt();    // 总钱数       
        int m = scanner.nextInt();    // 购买物品个数或物品id
        int[] dp=new int[N+1];
        // 分组，0为主件，1为附件1，2为附件2
        int[][] price=new int[60][3];    // 物品价格
        int[][] value=new int[60][3];    // 物品价值
        for(int i=1;i<=m;i++){
            int p=scanner.nextInt();
            int v=scanner.nextInt();
            int q=scanner.nextInt();
            if(q==0){
                price[i][0]=p;
                value[i][0]=p*v;
            }
            //注意q为主件id对应的附件，price[q][1]为0,则默认选主件q对应的附件1
            else if(price[q][1]==0){
                price[q][1]=p;
                value[q][1]=p*v;
            }
            //如果附件1已经有了，则作为附件2
            else{
                price[q][2]=p;
                value[q][2]=p*v;
            }             
        }
        for(int i=1;i<=m;i++){
            for(int j=N;j>=0&&price[i][0]!=0;j--){
                //主件的情况
                if(j>=price[i][0]){
                    dp[j]=Math.max(dp[j],dp[j-price[i][0]]+value[i][0]);
                }
                //主件和附件1的情况
                if(price[i][1]!=0&&j>=price[i][0]+price[i][1]){                   
                    dp[j]=Math.max(dp[j],dp[j-price[i][0]-price[i][1]]+value[i][0]+value[i][1]);                   
                }
                //主件和附件2的情况
                if(price[i][2]!=0&&j>=price[i][0]+price[i][2]){                   
                    dp[j]=Math.max(dp[j],dp[j-price[i][0]-price[i][2]]+value[i][0]+value[i][2]);                   
                }
                //主件和两个附件的情况
                if(price[i][1]!=0&&price[i][2]!=0&&j>=price[i][0]+price[i][1]+price[i][2]){
                    dp[j]=Math.max(dp[j],dp[j-price[i][0]-price[i][1]-price[i][2]]+value[i][0]+value[i][1]+value[i][2]);                    
                }
            }
        }
        System.out.println(dp[N]);
    }   
}

3.复杂度分析

• 时间复杂度：两层循环，最多执行$m\ast (N+1)m*(N+1)$次，所以时间复杂度为$O(m\ast N)O(m*N)$。
• 空间复杂度：需要额外大小为$N+1N+1$的dp数组，所以空间复杂度为$O(N)O(N)$。