本题是背包问题，可是须要转化成背包的。

由于是两个人洗衣服，那么就是说一个人仅仅须要洗一半就能够了，由于不能两个人同一时候洗一件衣服，所以就成了01背包问题了。

思路：

1 计算洗完同一颜色的衣服须要的总时间totTime

2 利用动态规划背包法求这些衣服能在那些时间点完毕

3 求比(totTime+1)/2大的最小时间点

4 得到洗一种颜色衣服的时间，那么继续求下洗一种颜色衣服的时间

5 最后加起来就是答案了。

这个是算法问题。

剩下来就是考编程功力了。由于给出的数据，须要我们自己把衣服分类，分类之后再对每一种颜色衣服进行动态规划法。

会使用map就不难了。

我这里是使用map，然后把颜色转化为整数，然后利用vector容器保存分类结果的。

用好vector也不用操心数组不够大的问题，只是vector却是比一般数组慢一点点的。

#include <stdio.h>

#include <map>

#include <string>

#include <vector>

using std::map;

using std::string;

using std::vector;

int bagDP(vector<vector<int> > &cl)

{

	int washTime = 0;

	for (int i = 0; i < (int)cl.size(); i++)

	{

		int totTime = 0;

		for (int j = 0; j < (int)cl[i].size(); j++)

			totTime += cl[i][j];

		vector<bool> tbl(totTime+1);

		tbl[0] = true;

		for (int j = 0; j < (int)cl[i].size(); j++)

		{

			for (int t = totTime; t >= cl[i][j]; t--)

				if (tbl[t-cl[i][j]]) tbl[t] = true;

		}

		int t = (totTime+1)>>1;

		for ( ; t <= totTime && !tbl[t]; t++);

		washTime += t;

	}

	return washTime;

}

int main()

{

	int colorM, clothN, time;

	char col[12];

	while (scanf("%d %d", &colorM, &clothN) && colorM)

	{

		map<string, int> siMp;//for classifying

		string s;

		int c = 0;

		for (int i = 0; i < colorM; i++)

		{

			scanf("%s", col);

			s = col;

			siMp[s] = c++;

		}

		vector<vector<int> > clothes(siMp.size());

		for (int i = 0; i < clothN; i++)

		{

			scanf("%d %s", &time, col);

			s = col;

			clothes[siMp[s]].push_back(time);

		}

		siMp.clear();

		printf("%d\n", bagDP(clothes));

	}

	return 0;

}