背包问题之poj3211

题意：有m (1~10)种不同颜色的衣服总共n (1~100)件，Dearboy和她的girlfriend两个人要一起洗完全部衣服，为了预防色彩混合，他们不能同时洗不同颜色的衣服，给出洗完每件衣服所需的时间cloth[i].tim和它的颜色cloth[i].col，求出Dearboy和她的girlfriend最少用多少时间能洗完全部衣服。

 

思路：01背包，由于各种颜色互相独立，故把每种颜色都化为一个01背包，求出洗完每种颜色衣服的最短时间，它们的总和即为答案。首先按颜色对衣服进行归类，即将相同颜色的衣服放在同一类中
对于某一种颜色的所有衣服所需要的最少时间，相当于将这堆衣服按时间分为两推，使得这两堆衣服所需要的时间尽可能的接近。对于每堆衣服建模：  假设当前这堆衣服一个人洗的时间为sum, 令mid = sum/2;
  问题转化为，（1）有背包容量为mid,现在要从这堆衣服中选取衣服，使得总容量尽可能接近于mid
  继续转化..（2）背包容量为mid,某件衣服的重量为wi,价值也为wi,计算所能达到的最大价值 dp[mid],
  那么问题（2）中的dp[mid]相当于问题（1）中最接近于mid的那个容量，故原问题中这堆衣服所需要的实际时间为sum - dp[mid];

代码如下：

#include <iostream>
#include <string.h>
#include <vector>
using namespace std;
const int M=10;
const int N=100;
char color[M][N];
vector<int>cost[M];
int dp[100002];

int Max(int a,int b)
{
	return a>b?a:b;
}

int main()
{
	int n,m;
	while (scanf("%d%d",&m,&n)!=EOF)
	{
		if(m==0&&n==0)
			break;
		int i,j;
		for (i=0;i<m;i++)
		{
			cin>>color[i];
			cost[i].clear();
		}
		while (n--)
		{
			char col[N];
			int time;
			cin>>time>>col;
			for (i=0;i<m;i++)
				if(strcmp(color[i],col)==0)
					break;
				if(i<m)
				{
					cost[i].push_back(time);
				}
		}
		int ans=0;
		for (i=0;i<m;i++)
		{
			memset(dp,0,sizeof(dp));
			int sz=cost[i].size();
			int k,mid,sum=0;
			for (j=0;j<sz;j++)
				sum+=cost[i][j];
			mid=sum/2;
			for (j=0;j<sz;j++)
			{
				for (k=mid;k>=cost[i][j];k--)
				{
					dp[k]=Max(dp[k],dp[k-cost[i][j]]+cost[i][j]);
				}
			}
			ans=ans+sum-dp[mid];
		}
		cout<<ans<<endl;
	}
	return 0;
}