JAVA题解 | 01背包

import java.util.ArrayList;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] a = new int[n];
        int sum = 0;
        for (int i = 0; i < n; i++) {
            a[i] = in.nextInt();
            sum += a[i];
        }
        if (sum % 2 == 1) {
            System.out.println(-1);
            return;
        }
        sum /= 2;
        ArrayList<Integer>[] dp = new ArrayList[sum + 1];
        dp[0] = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            for (int j = sum; j >= 0; j--) {
                int k = j + a[i];
                if (dp[j] != null && k <= sum && dp[k] == null) {
                    dp[k] = new ArrayList<>(dp[j]);
                    dp[k].add(i);
                }
            }
        }
        if (dp[sum] == null) {
            System.out.println(-1);
            return;
        }
        dp[sum].sort(Integer::compareTo);
        ArrayList<Integer> l = dp[sum];
        ArrayList<Integer> r = new ArrayList<>();
        for (int i = 0, t = 0; i < n; i++) {
            if (t >= l.size() || l.get(t) != i) r.add(i);
            else t++;
        }
        ArrayList<Pair> ans = new ArrayList<>();
        for (Integer i : l) {
            for (Integer j : r) {
                if (a[i] == 0) break;
                while (a[i] > 0 && a[j] > 0) {
                    ans.add(new Pair(i + 1, j + 1));
                    a[i]--;
                    a[j]--;
                }
            }
        }
        System.out.println(ans.size());
        for (Pair an : ans) {
            System.out.printf("%d %d\n", an.a, an.b);
        }
        in.close();
    }

    public static class Pair {
        Integer a, b;

        public Pair(Integer a, Integer b) {
            this.a = a;
            this.b = b;
        }
    }
}

总度数是奇数时无解。

通过dp找任意个点组成度数和为总度数一半的情况，有的话有解，把这种组合中没出现过的点放到二分图右部，然后暴力连边