用iava给定n个集合, 要求选出其中某些集合, 使得这些集合的并集的势, 等于选出的集合的数目. 对于任意的k(1< =k< =n), 满从中选出任意k个集合, 这k个集合的并集的势一定大于等于k. 每个集合有一个权值, 每个选择方案的代价是所选的集合的权值的和. 请输出代价最小的选择方案的代价. 当然, 不选择任何一个集合是一个可行的方案(权值和为0), 但不一定最优(权值和可以为负). 输入格式 第一行一个正整数n(1< =n< =300), 为集合个数. 在接下来n行中, 第i行描述第i个集合: 首先给出一个正整数m[i]为该集合的势, 显然1< =m[i]< =n. 接下来m[i]个在1到n之间的整数, 表示该集合中的元素. 最后一行n个整数, 为每个集合的权值, 绝对值不超过1e6. 输出格式 仅一个整数, 为代价最小的选择方案的代价. 样例输入 3 1 1 2 2 3 1 3 10 20 -3 样例输出 -3 样例输入 5 2 1 2 2 2 3 2 3 4 2 4 5 2 5 1 1 -1 1 -1 1 样例输出 0 样例输入 5 2 1 2 2 2 3 2 3 4 2 4 5 2 5 1 -1 1 -1 1 -1 样例输出 -1

该问题可以使用动态规划来解决。设 $f[S]$ 表示选择的集合对应的二进制状态为 $S$ 时的最小代价。

状态转移方程为：

$$f[S] = \min\{f[S\setminus T] + w[T]\}$$

其中 $T$ 是 $S$ 的一个子集，$S\setminus T$ 表示从 $S$ 中去掉 $T$ 后的集合，$w[T]$ 表示选择集合 $T$ 的权值和。

初始状态为 $f[0] = 0$，表示不选择任何集合的代价为 0。

最终答案为 $f[(1<<n)-1]$，表示选择所有集合的代价。

下面是Java语言的代码实现：

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static int INF = 0x3f3f3f3f;
    static int[] m;
    static int[] w;
    static int[][] s;
    static int[][] f;

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        m = new int[n+1];
        s = new int[n+1][n+1];
        w = new int[n+1];
        f = new int[1<<n][n+1];
        for (int i = 1; i <= n; i++) {
            m[i] = input.nextInt();
            for (int j = 0; j < m[i]; j++) {
                int x = input.nextInt();
                s[i][x] = 1;
            }
        }
        for (int i = 1; i <= n; i++) {
            w[i] = input.nextInt();
        }
        Arrays.fill(f, INF);
        f[0][0] = 0;
        for (int S = 0; S < 1<<n; S++) {
            int cnt = 0;
            for (int i = 1; i <= n; i++) {
                if ((S>>(i-1) & 1) == 1) {
                    cnt++;
                }
            }
            for (int i = 1; i <= n; i++) {
                if ((S>>(i-1) & 1) == 1) {
                    for (int j = 1; j <= m[i]; j++) {
                        int x = s[i][j];
                        if ((S>>(x-1) & 1) == 0) {
                            S |= 1<<(x-1);
                            cnt++;
                        }
                    }
                }
            }
            for (int T = S; T > 0; T = (T-1) & S) {
                int nw = cnt - Integer.bitCount(T);
                if (nw <= 0) {
                    continue;
                }
                int sum = 0;
                for (int i = 1; i <= n; i++) {
                    if ((T>>(i-1) & 1) == 1) {
                        sum += w[i];
                    }
                }
                for (int i = 0; i <= n; i++) {
                    f[S][i+nw] = Math.min(f[S][i+nw], f[S-T][i]+sum);
                }
            }
        }
        int ans = INF;
        for (int i = 1; i <= n; i++) {
            ans = Math.min(ans, f[(1<<n)-1][i]);
        }
        System.out.println(ans);
    }
}

时间复杂度为 $O(3^n n^2)$。