学步园

http://poj.org/problem?id=3211

按颜色分类，然后每种颜色的进行01背包即可。 无聊的题~~~~~~

code:

#include <iostream>
#include <cstring>
using namespace std;
const int maxn = 102;
const int maxm = 12;
struct tt {
     char clr[11];
     int cnt;
     int sum;
     int pdt[maxn];
} colors[maxn];
bool f[500005];
int main()
{
     int i, j, k, n, m, ans, mid;
     int x;
     char tmp[11];
     while(cin>>m>>n) {
          if(n==0&&m==0) break;
          for(i=0; i<m; i++) {
               cin>>tmp;
               strcpy(colors[i].clr, tmp);
               colors[i].cnt = 0;
               colors[i].sum = 0;
          }
          for(i=0; i<n; i++) {
               cin>>x>>tmp;
               for(j=0; j<m; j++)
                    if(strcmp(tmp,colors[j].clr)==0) {
                         colors[j].sum += x;
                         colors[j].pdt[ colors[j].cnt++ ] = x;
                    }
          }
//        for(i=0; i<m; i++)
//        cout<<colors[i].sum<<"   "<<colors[i].clr<<endl;
          //dp
          ans = 0;
          for(k=0; k<m; k++)
               if(colors[k].cnt>0) {
                    mid = colors[k].sum/2;
                    memset(f,0,sizeof(f));
                    f[0] = 1;
                    for(i=0; i<colors[k].cnt; i++)
                         for(j=mid; j>=colors[k].pdt[i]; j--)
                              f[j] = f[j] || f[j- colors[k].pdt[i] ];
                    for(i=mid; i>=0; i--)
                         if(f[i]) break;
                    ans += (colors[k].sum - i);
               }
          cout<<ans<<endl;
     }
     return 0;
}