动态规划(hdoj3006):数字集合

有n个集合(1<=n<=100)，n个集合中有k个数字,每个数字的值v(1<=v<=m),并且1<=m<=14。

重组这n个集合，他们能构成多少种不同的集合？

input:

4 4

1 1

1 2

1 3

1 4

2 4

3 1 2 3

4 1 2 3 4

数字的第一行是两个数字，第一个数字是n,第二个数字是m。接下来的n行描述了n个集合。

其中每行的第一个数字代表这个集合中的数字个数k,接下来的k个数字是这个集合中的每个元素。

例如第二个输入。

有2个集合，集合的最大值是4.

集合1有3个元素，分别为1 2 3

集合2有4个元素，分别为1 2 3 4

题解：

1.用bit表表示集合。这个方法在《编程珠玑》头开始就介绍了。

对于集合 比如1,2,3 使用0111表示， 1,2,3,4则是1111.

数字是几，哪一位就设置成1.

这样两个集合的并集，就是 0111 & 1111 = 1111

2.完成格式化输入后，就是一个简单的动态规划问题。属于01背包问题。

/*
 * =====================================================================================
 *
 *       Filename:  numset.c
 *
 *    Description:
 *
 *        Version:  1.0
 *        Created:  10/17/2012 06:27:06 PM
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  [e-mail] (),
 *   Organization:
 *
 * =====================================================================================
 */
#include <stdlib.h>

#include <stdio.h>

#define    MAX (1<<14)-1            /*  */

#define    M 14            /*  */
#define N 100
char result[MAX] = {0};
void test(int sets[], int count){
    result[0] = 1;
    int i = 0;
    for(;i<count;i++){
        int j = 0;
        for(;j<MAX;j++){
            if(result[j] == 1){
                result[j|sets[i]] = 1;
            }
        }
    }
}
int* formatinput(int ain[][10], int size){
    int *res = (int*)malloc(sizeof(int)*size);
    int i = 0;
    for(;i<size;i++){
        int t = 1;
        int v = 0;
        for(;t<=ain[i][0];t++){
            v|=(1<<(ain[i][t]-1));
        }
        res[i] = v;
    }
    return res;
}
/*
 * ===  FUNCTION  ======================================================================
 *         Name:  main
 *  Description:
 * =====================================================================================
 */
    int
main ( int argc, char *argv[] )
{
    int ain[][10] = {{3,1,2,3},{4,1,2,3,4}};
    int size = sizeof(ain)/sizeof(int)/10;
    int * input = formatinput(ain, size);
    test(input, size);
    int i = 1;
    int count = 0;
    for(;i<MAX;i++){
        if(result[i] == 1) count++;
    }
    printf ( "%d\n", count );
    return EXIT_SUCCESS;
}                /* ----------  end of function main  ---------- */

您没有插入代码！