poj 3211 Washing Clothes (分组背包)

 1 /*************************************
 2 
 3 题目：    Washing Clothes（poj 3211）
 4 链接：    http://poj.org/problem?id=3211
 5 算法：    分组背包
 6           由于题目有字符串不好处理，用map
 7           函数来处理后做法和一般分组背包
 8           一样了。然后对没中颜色做01背包
 9           就可以了。
10 
11 **************************************/
12 
13 
14 #include<iostream>
15 #include<map>
16 #include<cstdio>
17 #include<cstring>
18 using namespace std;
19 
20 map<string,int>g1,g2;        ///g1记录每个颜色出现的循序，
21                              ///g2记录每个颜色出现的次数。
22 
23 int a[15][150];
24 char s[150][15];
25 int dp[10000];
26 
27 int main()
28 {
29     int n,m,i,j,k;
30     while (~scanf("%d%d",&n,&m))
31     {
32         if (n==0&&m==0) return 0;
33         g1.clear();
34         g2.clear();
35         for (i=0;i<n;i++)
36         {
37             scanf("%s",&s[i]);
38             g1[s[i]]=i;
39         }
40         while (m--)
41         {
42             char s[15];
43             int x;
44             scanf("%d %s",&x,&s);
45             a[g1[s]][g2[s]++]=x;
46         }
47         int ans=0;
48 
49         /// 分组背包
50         for (i=0;i<n;i++)
51         {
52             memset(dp,0,sizeof(dp));
53             int cut=0;
54             for (j=0;j<g2[s[i]];j++) cut+=a[i][j];
55             for (j=0;j<g2[s[i]];j++)      ///01背包
56             {
57                 for (k=cut/2;k>=a[i][j];k--)
58                 dp[k]=max(dp[k],dp[k-a[i][j]]+a[i][j]);
59             }
60             ans+=cut-dp[cut/2];
61         }
62         cout<<ans<<endl;
63     }
64 }