二维的01背包问题（附加组合背包）

  1. 按照一维背包（基础背包）的思路解题即可。
  2. 设dp[i][j][k]表示前i个物品（包括i）、在j的cost下、在k的人数限制下的最大战力。这个时候，需要特殊处理i=0的情况。
  3. 还有一种写法就是：dp[i][j][k]表示前i个物品（不包括i）、在j的cost下、在k的人数限制下的最大战力。i维度要+1，而且dp遍历的时候，i也从1开始。带来的一个情况就是在找最大值的时候，不能单纯的从i和j的最大值开始找（遍历k），而是连j也要遍历去找。仿佛是要把两个维度的空间都搜索一遍似的。
  4. 无论那种写法，都要注意排除前驱黑洞的情况。这种情况是不能迭代的。

具体的代码如下：

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int n = in.nextInt();
        int C = in.nextInt();
        int m = in.nextInt();
        int[] a = new int[n];//cost
        int[] b = new int[n]; //战力
        int[] pair = new int[n]; //双生英雄
        Arrays.fill(pair, -1);
        long[] pairValue = new long[n];//
        for (int i = 0; i < n; i++) {
            a[i] = in.nextInt();
            b[i] = in.nextInt();
        }
        for (int i = 0; i < m; i++) {
            int h1 = in.nextInt();
            int h2 = in.nextInt();
            int v = in.nextInt();
            pair[h1 - 1] = h2 - 1;
            pair[h2 - 1] = h1 - 1;
            pairValue[h1 - 1] = v;
            pairValue[h2 - 1] = v;
        }
        boolean[] visited = new boolean[n];
        //一个group就是一个01背包啦，只不过这个背包不再简单的装和不装的情况，而是更多的情况了，这就是组合背包问题。
        List<List<PackageItemOption>> groups = new ArrayList<>();
        for (int i = 0; i < pair.length; i++) {
            if (visited[i]) {// 双生英雄之后一个英雄，已经在前面处理了。
                continue;
            }
            List<PackageItemOption> options = new ArrayList<>();
            // 不取任何该英雄
            options.add(new PackageItemOption(0, 0, 0));
            // 取该英雄
            options.add(new PackageItemOption(1, a[i], b[i]));
            if (pair[i] >= 0) {
                // 双生英雄
                int pairIdx = pair[i];
                // 取另外一个英雄
                options.add(new PackageItemOption(1, a[pairIdx], b[pairIdx]));
                // 取双生英雄
                options.add(new PackageItemOption(2, a[i] + a[pairIdx], b[i] + b[pairIdx] + pairValue[i]));
                visited[pairIdx] = true;
            }
            visited[i] = true;
            groups.add(options);
        }
        // dp[i][j][k]表示前i个物品（包括i）、在j的cost下、在k的人数限制下的最大战力
        long[][][] dp = new long[groups.size()][C + 1][4 + 1];
        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j < dp[0].length; j++) {
                Arrays.fill(dp[i][j], NEG);
            }
        }
        dp[0][0][0] = 0; //源头
        for (int i = 0; i < dp.length; i++) {
            List<PackageItemOption> options = groups.get(i);
//            List<PackageItemOption> options = groups.get(i - 1);
            for (int j = 0; j < dp[0].length; j++) {
                for (int k = 0; k < dp[0][0].length; k++) {
                    for (PackageItemOption option : options) {
                        int cost = option.cost;
                        int people = option.people;
                        long value = option.value;
                        if (i == 0) {
                            if (j >= cost && k >= people) {
                                dp[i][j][k] = Math.max(dp[i][j][k], value);
                            }
                            continue;
                        }
                        if (j >= cost && k >= people && dp[i - 1][j - cost][k - people] != NEG) {
                            // 注意以上三个条件，特别是第三个，因为我们初始化的时候值最dp[0][0][0]做了初始化，
                            // 会存在一些漏洞。第三个条件成立说明确实有过这样的01背包解法。
                            dp[i][j][k] = Math.max(dp[i][j][k], dp[i - 1][j - cost][k - people] + value);
                        }
                    }
                }
            }
        }
        long max = 0;
        for (int j = 0; j <= C; j++) {
            for (int k = 0; k <= 4; k++) {
                max = Math.max(max, dp[dp.length - 1][j][k]);
            }
        }
        System.out.println(max);
    }

    public static long NEG = Long.MIN_VALUE / 2;


    // 背包要装的子物品
    public static class PackageItemOption {
        public int people;
        public int cost;
        public long value;

        public PackageItemOption(int p, int c, long v) {
            this.people = p;
            this.cost = c;
            this.value = v;
        }
    }
}