简单01背包 POJ3211 Washing Clothes 多种衣服分别dp
生活随笔
收集整理的這篇文章主要介紹了
简单01背包 POJ3211 Washing Clothes 多种衣服分别dp
小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.
題目連接:http://poj.org/problem?id=3211
大意就是 一個人洗衣服,然后找他媳婦幫忙。有n種顏色的衣服,和m件衣服,每件衣服的顏色和洗出來的時間都會給出來。再洗的時候兩個人不能同時洗一件衣服,但是可以洗兩件衣服,但是不同種顏色的衣服不能同時洗~讓你求所需要的最少時間。
這樣我們就可以知道,這道題就是對每一種顏色的衣服所需要的時間進行dP就OK了,對每一種顏色的衣服DP就相當于給你幾個正數(shù)讓你把他分的盡量平均,也就是把和加起來然后除以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的全部內容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: 重复数据删除(De-duplicatio
- 下一篇: siege用法