poj3211(Washing Clothes + 0/1背包)
题目链接：http://poj.org/problem?id=3211
题意：Dearboy夫妇有一桶衣服要清洗，由于衣服颜色不同，质量也不太好，为了防止不同颜色的衣服混合清洗造成染色，所以Dearboy夫妇只能在清洗完一种颜色的衣服后再清洗另一种颜色的衣服（注意理解：如果Dearboy的老婆已经把蓝色衣服洗好了，但Dearboy洗的那一件蓝色衣服还没有清洗好，Dearboy的老婆只能等着，等Dearboy把他洗的蓝色衣服洗好了，才能一起再去洗黄色的衣服）。现有M种颜色的衣服N件，每件衣服的清洗需要的时间和颜色题目告知，问Dearboy夫妇至少需要多少时间能把衣服清洗干净。
思路：由于Dearboy夫妇只能在清洗完一种颜色的衣服后才能清洗另一种颜色的衣服，所以就要求Dearboy夫妇再清洗一种颜色的衣服时花的时间尽可能的相同。假设清洗一种颜色的衣服需要的额总时间为sumtime,将sumtime/2的背包尽可能的装满，清洗该种衣服所需要的时间则为sumtime-dp[sumtime/2]（以时间长的一个为准）;
代码：
#include<stdio.h>#include<string.h>#include<stdlib.h>#define MAXM 15#define MAXN 105int M,N,ans;char color[MAXM][11];int dp[50005];struct Close{int time;char col[11];int used;}close[MAXN];int max(int a,int b){return a>b ? a : b ;}int main(){ int i,j; while(scanf("%d%d",&M,&N) && (M!=0&&N!=0)) { ans =0; for(i=0;i<M;i++) scanf("%s",color[i]); for(i=0;i<N;i++) { scanf("%d %s",&close[i].time,&close[i].col); close[i].used=0; } int temp[105]; for(i=0;i<M;i++)//一种颜色一种颜色的清洗 { int num=0; int sumtime=0; for(j=0;j<N;j++)//求出一种颜色的衣服总共要花费多少时间清洗（sumtime） { if(close[j].used) continue; if(strcmp(color[i],close[j].col) == 0) { temp[num++]=close[j].time; sumtime += close[j].time; close[j].used = 1; } } for(int l=0;l<=sumtime/2;l++) dp[l]=0; for(int k=0;k<num;k++)//背包sumtime/2最大装满 for(int v=sumtime/2;v>=temp[k];v--) { dp[v] = max(dp[v],dp[v-temp[k]]+temp[k]); }ans += sumtime - dp[sumtime/2];//清洗一种颜色衣服需要花费的时间 } printf("%d\n",ans); } return 0;}