简单01背包 POJ3211 Washing Clothes 多种衣服分别dp

题目连接：http://poj.org/problem?id=3211

大意就是 一个人洗衣服，然后找他媳妇帮忙。有n种颜色的衣服，和m件衣服，每件衣服的颜色和洗出来的时间都会给出来。再洗的时候两个人不能同时洗一件衣服，但是可以洗两件衣服，但是不同种颜色的衣服不能同时洗~让你求所需要的最少时间。

这样我们就可以知道，这道题就是对每一种颜色的衣服所需要的时间进行dP就OK了，对每一种颜色的衣服DP就相当于给你几个正数让你把他分的尽量平均，也就是把和加起来然后除以2作为背包容量~

代码：

#include <stdio.h> #include <string.h>struct node {char color[20];int sum;int a[105];int count;//记录有多少见这种颜色的衣服。 }col[15]; int count; int search(char s[],int m) {int i;for(i = 0;i < m;i++)if(strcmp(s,col[i].color) == 0)return i;return 0; } int main() {char str[15];int m,n,i,j,a,k;int f[2000];while(scanf("%d %d",&m,&n) && n||m){count = 0;for(i = 0;i < m;i++){scanf("%s",col[i].color);col[i].sum = 0;col[i].count = 0;}for(i = 0;i < n;i++){scanf("%d %s",&a,str);int leap;leap = search(str,m);int tag;tag = col[leap].count;col[leap].a[tag] = a;col[leap].sum += a;col[leap].count++;}int sum = 0;for(i = 0;i < m;i++){memset(f,0,sizeof(f));int v = col[i].sum/2;for(j = 0;j < col[i].count;j++)//对每一种进行DPfor(k = v;k >= col[i].a[j];k--)if(f[k] < f[k-col[i].a[j]]+col[i].a[j])f[k] = f[k-col[i].a[j]]+col[i].a[j];sum += col[i].sum-f[v];//必须让两个人里边用时最多的加到sum里面去，因为最多的那个才是他们的时间 }printf("%d\n",sum);}return 0; }

转载于:https://www.cnblogs.com/0803yijia/archive/2012/08/14/2637284.html

总结

以上是生活随笔为你收集整理的简单01背包 POJ3211 Washing Clothes 多种衣服分别dp的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。