#include <iostream>
using namespace std;

int m,n,pieces[10],time[11][101],cost[101][100000];
char color[10][11];

struct{
	int time;
	char color[11];
}clothes[101];

int findcolor(int j)
{
	for(int i=1;i<=m;i++)
		if(!strcmp(color[i],clothes[j].color))
			return i;
	return 0;
}

int main(int argc, char* argv[])
{
	
	while(cin>>m>>n&&m+n)
	{
		memset(pieces,0,sizeof(pieces));
		for(int i=1;i<=m;i++)
			cin>>color[i];
		for(i=1;i<=n;i++)
		{
			cin>>clothes[i].time>>clothes[i].color;
			int t=findcolor(i);
			time[t][++pieces[t]]=clothes[i].time;
		}
		int total=0;
		for(i=1;i<=m;i++)
		{
			int w=0;
			for(int j=1;j<=pieces[i];j++)
				w+=time[i][j];
			memset(cost,0,sizeof(cost));
			for(j=1;j<=pieces[i];j++)
				for(int k=1;k<=w/2;k++)
				{
					cost[j][k]=cost[j-1][k];
					if(k>=time[i][j]&&cost[j-1][k-time[i][j]]+time[i][j]>cost[j][k])
						cost[j][k]=cost[j-1][k-time[i][j]]+time[i][j];
				}
			total+=w-cost[pieces[i]][w/2];
		}
		cout<<total<<endl;
	}
	return 0;
}

• Re:TLE,用的背包DP？？？？？？？？？？？ (61) kyxyljb 2009-08-11 15:00:49