HJ16 购物单 | 题解

设主件个数为n，奖金数量为M，每个主件对应的价格为v，每个主件对应的重要程度为w。d[i][j]表示从前i个主件中选取，奖金数量为j的情况下，所获得的最大价格*重要程度累加和。另外注意到一个小细节：每个主件只能有0～2个附件，最多才4种搭配方式(00,01,10,11)，得到如下状态公式：

1. 如果j>=v[i-1]，那么dp[i][j] = max(dp[i][j-v[i-1]]+v[i-1]*w[i-1], dp[i-1][j], ➜➜➜➜)（➜➜➜➜表示有附件的情况）
2. 如果j<v[i-1]，那么dp[i][j] = dp[i-1][j]
3. 基准1: dp[0][..]=0
4. 基准2: dp[..][0]=0

对于状态公式的解释：

1. 如果总奖金数能涵盖当前物品，那么选取包含当前物品和不包含当前物品两种情况下最大的累加和
2. 如果总奖金数不能涵盖当前物品，那么直接取前i-1个物品的最大累加和
3. 基准1: 商品个数为0，再怎么加也是0
4. 基准2: 总奖金数为0，同样再怎么加也是0

上面的这些，除了➜➜➜➜之外的其他部分，和0/1背包问题完全一致，接下来分析➜➜➜➜:

1. 如果没有附件，则跳过
2. 如果附件数为1，且总奖金容得下附件，那么取最大值
3. 如果附件数为2...

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int N = sc.nextInt();
            int m = sc.nextInt();
            N /= 10;
            int[][] prices = new int[61][3];
            int[][] priority = new int[61][3];
            for (int i = 1; i <= m; ++i) {
                int a = sc.nextInt(), b = sc.nextInt(), c = sc.nextInt();
                a /= 10; b *= a;
                if (c == 0) {
                    prices[i][0] = a;
                    priority[i][0] = b;
                } else {
                    if (prices[c][1] == 0) {
                        prices[c][1] = a;
                        priority[c][1] = b;
                    } else {
                        prices[c][2] = a;
                        priority[c][2] = b;
                    }
                }
            }

            int[][] dp = new int[m + 1][N + 1];
            for (int i = 1; i <= m; ++i) {
                for (int j = 1; j <= N; ++j) {
                    int a = prices[i][0], b = priority[i][0];
                    int c = prices[i][1], d = priority[i][1];
                    int e = prices[i][2], f = priority[i][2];
                    dp[i][j] = j >= a ? Math.max(dp[i - 1][j - a] + b, dp[i - 1][j]) : dp[i - 1][j];
                    dp[i][j] = j >= (a + c) ? Math.max(dp[i - 1][j - a - c] + b + d, dp[i][j]) : dp[i][j];
                    dp[i][j] = j >= (a + e) ? Math.max(dp[i - 1][j - a - e] + b + f, dp[i][j]) : dp[i][j];
                    dp[i][j] = j >= (a + c + e) ? Math.max(dp[i - 1][j - a - c - e] + b + d + f, dp[i][j]) : dp[i][j];
                }
            }
            System.out.println(dp[m][N] * 10);
        }
    }
}