题解 | #华为no.16 购物单#

如果不考虑主件、附件问题，这就是一个01背包问题，解法为dp[i][j] = Math.max(dp[i-1][j],value+dp[i-1][j-weight]) 但是此题需要考虑附件，所以就如下所示

public class Main {
    public static void main(String[] args) {
        //01背包问题
        Scanner sc = new Scanner(System.in);
            int N = sc.nextInt()/10; //总价格，除以10优化
            int m = sc.nextInt();    //总共有m种
            int[][] price = new int[m+1][3];
            int[][] ww = new int[m+1][3];
            for (int i = 1; i <= m ; i++) {
                int v = sc.nextInt()/10;
                int p = sc.nextInt()*v;
                int q =sc.nextInt();
                if (q==0) {//主件
                    price[i][0] = v;
                    ww[i][0] = p;
                } else if (price[q][1]==0) {//附件1
                    price[q][1] = v;
                    ww[q][1] = p;
                } else {//附件2
                    price[q][2] = v;
                    ww[q][2] = p;
                }
            }
            int[][] dp = new int[m+1][N+1];
            for (int i = 1; i <=m; i++) {
                for (int j = 1; j <=N; j++) {
                    //主件的价格和重要度
                    int a = price[i][0];
                    int b = ww[i][0];
                    //附件1的价格和重要度
                    int c = price[i][1];
                    int d = ww[i][1];
                    //附件2的价格和重要度
                    int e = price[i][2];
                    int f = ww[i][2];
                    dp[i][j] = j>=a ? Math.max(b+dp[i-1][j-a],dp[i-1][j]) :dp[i-1][j];
                    dp[i][j] = j>=a+c ? Math.max(b+d+dp[i-1][j-a-c],dp[i][j]) :dp[i][j];
                    dp[i][j] = j>=a+e ? Math.max(b+f+dp[i-1][j-a-e],dp[i][j]) :dp[i][j];
                    dp[i][j] = j>=a+c+e ? Math.max(b+d+f+dp[i-1][j-a-c-e],dp[i][j]) :dp[i][j];

                }

            }
            System.out.println(dp[m][N]*10);


    }

}