背包"/>
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;
}
更多推荐
01分组背包
发布评论