Description

Input

Output

Sample Input

3 4

red blue yellow

2 red

3 blue

4 blue

6 red

0 0

Sample Output

10

这道题是分组背包的变形，先用map把每个字符串相应每个数字，然后把同样的字符串归为一类，求出最小的时间，然后累加即可了，这里每一组的最短时间能够用01背包。由于是两人同一时候做，能够知道两人的工作量相差最小时。结束这样的颜色的衣服所用的时间最少。所以能够设背包容量为sum[i]/2,然后求这个容量下的最打容量。然后这组所加的时间就是sum[i]-dp[sum[i]/2].这里还要注意一点，初始化的时候不能初始化为-1，然后将dp[0]=0,由于不一定要恰好，细致理解一下：）

#include<iostream>

#include<stdlib.h>

#include<stdio.h>

#include<string.h>

#include<math.h>

#include<vector>

#include<map>

#include<queue>

#include<stack>

#include<string>

#include<algorithm>

using namespace std;

int a[15][106],num[106],sum[106],dp[100500];

int main()

{

	int n,m,i,j,t,c,ans,liang,k,num1;

	char s[20];

	map<string,int>hash;

	while(scanf("%d%d",&n,&m)!=EOF)

	{

		if(n==0 && m==0)break;

		memset(a,0,sizeof(a));

		memset(num,0,sizeof(num));

		memset(sum,0,sizeof(sum));

		memset(s,0,sizeof(s));

		hash.clear();

		num1=0;

		for(i=1;i<=n;i++){

			scanf("%s",s);

			if(hash[s]==0){

				num1++;hash[s]=num1;

			}

		}

		for(i=1;i<=m;i++){

			scanf("%d%s",&c,s);

			t=hash[s];

			a[t][++num[t]]=c;

			sum[t]+=c;

		}

		ans=0;

		for(i=1;i<=num1;i++){

			if(num[i]==0)continue;

			else{

				//memset(dp,-1,sizeof(dp));

				memset(dp,0,sizeof(dp));

				liang=sum[i]/2;

				for(k=1;k<=num[i];k++){

					for(j=liang;j>=a[i][k];j--){

						//if(dp[j-a[i][k]]!=-1)

						dp[j]=max(dp[j],dp[j-a[i][k]]+a[i][k]);

					}

				}

				ans=ans+sum[i]-dp[liang];

			}

		}

		printf("%d\n",ans);

	}

	return 0;

}