gzwzm06
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  1 随笔 :: 52 文章 :: 17 评论 :: 0 Trackbacks
POJ 3211 Washing Clothes
 1#include <cstdio>
 2#include <cstring>
 3
 4const int SIZE = 101;
 5const int MAX = 1000001;;
 6
 7int M, N;
 8int arr[10][SIZE], size[10], sum[10];
 9char cloth[10][11];
10bool dp[MAX];
11
12int GetType(const char* str)
13{
14    int i;
15    for ( i = 0; i < M; ++i )
16        if ( strcmp(str, cloth[i]) == 0 )
17            break;
18
19    return i;
20}
21
22void Solve()
23{
24    int i, v, n, t, limit;
25    int time = 0;
26
27    for ( n = 0; n < M; ++n )
28    {
29        memset(dp, 0, sizeof(dp));
30        dp[0] = true;
31
32        t = 0;
33        limit = sum[n] >> 1;                //01背包：dp出最接近 sum / 2 的值
34        for ( i = 0; i < size[n]; ++i )
35        {
36            for ( v = limit; v >= arr[n][i]; --v )
37            {
38                
39                if ( dp[v - arr[n][i]] )
40                {
41                    dp[v] = true;            //对该位置标志
42                    if ( v > t )
43                    {
44                        t = v;
45                    }
46                }
47
48            }
49        }
50        
51        time += (sum[n] - t);    //须取最大的值
52    }
53    
54
55    printf("%d\n", time);
56}
57
58int main()
59{
60//    freopen("1.txt", "r", stdin);
61
62    int i, j, n;
63    char str[11];
64
65    while ( scanf("%d %d", &M, &N) != EOF )
66    {
67        if ( M == 0 && N == 0 )
68            break;
69
70        for ( i = 0; i < M; ++i )
71        {
72            size[i] = 0;
73            sum[i] = 0;
74            scanf("%s", cloth[i]);
75        }
76
77        for ( i = 0; i < N; ++i )
78        {
79            scanf("%d %s", &n, str);
80
81            j = GetType( str );
82            arr[j][size[j]++] = n;
83            sum[j] += n;
84        }
85
86        Solve();
87    }
88
89    return 0;
90}
posted on 2009-05-03 11:03 巫 阅读(385) 评论(0)  编辑 收藏 引用 所属分类: DP

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理