01分组背包

背包"/>

01分组背包

题意：

两个人洗衣服， 有M种颜色的衣服共N件， 要求两人只能同时洗相同颜色的衣服， 求洗衣服的最短时间。        思路： 一开始以为是个贪心，WA了。搜了下发现是个01背包分组问题： 将衣服按种类分配好之后，既然是要求洗衣时间尽量少，每个人按每种颜色衣服的一半的时间来洗。转化为背包问题： 种类： 某种颜色衣服个数 价值： 所花时间 花费： 所花时间

#include <iostream>
#include <stdio.h>
#include <cstring>
using namespace std;
int m,n;
int dp[100005];
struct clothes
{char color[12];int num;int sum;int time[105];
}clo[11];
char t[105];
int main()
{while(~scanf("%d%d",&m,&n)){if(m==0&&n==0)break;memset(dp,0,sizeof(dp));int cot=0;for(int i=1;i<=m;i++){scanf("%s",clo[i].color);clo[i].num = clo[i].sum = 0;}int time;for(int i=1;i<=n;i++){scanf("%d %s",&time,t);for(int j=1;j<=m;j++){if(!strcmp(t,clo[j].color)){int tmp = clo[j].num;clo[j].time[tmp+1] = time;clo[j].sum += time;clo[j].num++;}}}int ans=0;for(int i=1;i<=m;i++){memset(dp,0,sizeof(dp));int voc=clo[i].sum/2;for(int j=1;j<=clo[i].num;j++){for(int k=voc;k>=clo[i].time[j];k--){dp[k]=max(dp[k],dp[k-clo[i].time[j]]+clo[i].time[j]);}}ans+=clo[i].sum-dp[voc];}cout<<ans<<endl;}return 0;
}