题解 | #购物单# (代码逐行解释)

import java.util.Scanner;

/**
01背包：dp[i][j]表示前i件物品，背包容量为j能够取得的最大价值
1.定义状态
附件不能独立存在，因此主件就是总的物件数量
附件情况分为以下四种：
主件 0
主件+附件1 1
主件+附件2 2
主件+附件1+附件2 3
用w[i][k]表示主件i且取k（0-3）种情况附件对应的价格
用v[i][k]表示主件i且取k种情况附件对应的重要度
2.转移方程：
现在就转为01背包问题了
dp[i][j]=max(dp[i-1][j]，dp[i-1][j-w[i][k]]+v[i][k])

 时间：O(n)
 空间：O(n^2)
 */
/*
1000 5
800 2 0
400 5 1
300 5 1
400 3 0
500 2 0

2200

50 5
20 3 5
20 3 5
10 3 0
10 2 0
10 1 0

130
 */
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 数据处理，转为目标数据结构
        int N = in.nextInt(), m = in.nextInt();
        int cnt = 0; // 主件数量
        int[][] arr = new int[m][3];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < 3; j++) {
                arr[i][j]=in.nextInt();
            }
            if (arr[i][2] == 0) {
                cnt++;
            }
        }
        int[][] w=new int[cnt][4], // 主件i和附件情况k的价格
        v=new int[cnt][4]; // 主件i和附件情况的满意度
        int i=0;
        for(int j=0;j<m;j++){
            if(arr[j][2]==0){ // 找到主件j
                w[i][0]=arr[j][0]; // 对应附件情况0
                v[i][0]=arr[j][0]*arr[j][1];
                for(int l=0;l<m;l++){ // 找到其它附件情况
                    if(arr[l][2]==j+1){ // 为主件j对应的附件
                        if(w[i][1]==0){ // 说明是附件1
                            w[i][1]=w[i][0]+arr[l][0]; // 附件情况1
                            v[i][1]=v[i][0]+arr[l][0]*arr[l][1];
                        }else{
                            w[i][2]=w[i][0]+arr[l][0]; // 附件情况2
                            v[i][2]=v[i][0]+arr[l][0]*arr[l][1];
                            w[i][3]=w[i][1]+w[i][2]-w[i][0]; // 附件情况3
                            v[i][3]=v[i][1]+v[i][2]-v[i][0];
                        }
                    }
                }
                i++; // 下一个主件
            }
        }
        // 套用01背包
        int[][] dp=new int[cnt+1][N+1];// 前i件主件，容量为N的最大价值
        int ans=0;
        for(int j=1;j<=cnt;j++){
            for(int t=0;t<=N;t++){
                // 不取或附件0123
                dp[j][t]=dp[j-1][t]; // 当前不取
                for(int l=0;l<=3;l++){
                    if(t>=w[j-1][l]){
                        dp[j][t]=Math.max(dp[j][t],dp[j-1][t-w[j-1][l]]+v[j-1][l]); // 附件0123
                    }
                }
            }
            ans=Math.max(ans,dp[j][N]);
        }
        System.out.println(ans);
    }
}