poj 3211 Washing Clothes(0/1背包)

点击打开链接poj 3211

思路: 0/1背包
分析:
1 题目要求洗完n件衣服所需的最少的时间，并且必须洗完一种颜色才能跳到下一种
2 仔细想想这一题和uva上面的一道分金币非常的相似，由于要求必须洗完一种颜色才能跳到下一种，那么我们只要使得洗每一种颜色的时间最少那么总的就最少，那怎样才能够最少的时间呢？也就是要求两个人的时间差最小(也就相当于一个人用一半的时间去能够洗的最多的衣服)，那么就转化为0/1背包的思想
3 做m次的dp然后求和即可

代码:

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int N = 15;
const int MAXN = 100010;

int m , n;
int w[N][N] , pos[N];
int sum[N] , dp[MAXN];
char color[N][N];

int returnIndex(char *str){
    for(int i = 1 ; i <= m ; i++)
        if(!strcmp(str , color[i]))
            return i;
}

int solve(){
    int ans = 0;
    for(int i = 1 ; i <= m ; i++){
        memset(dp , 0 , sizeof(dp)); 
        for(int j = 1 ; j <= pos[i] ; j++)
            for(int k = sum[i]/2 ; k >= w[i][j] ; k--)
                dp[k] = max(dp[k] , dp[k-w[i][j]]+w[i][j]); 
        ans += sum[i]-dp[sum[i]/2];
    }
    return ans;
}

int main(){
    char str[N];
    int x;
    while(scanf("%d%d" , &m , &n) && n+m){
        for(int i = 1 ; i <= m ; i++)
            scanf("%s" , color[i]); 
        memset(pos , 0 , sizeof(pos));
        memset(sum , 0 , sizeof(sum));
        for(int i = 1 ; i <= n ; i++){
            scanf("%d %s" , &x , str); 
            int index = returnIndex(str);
            pos[index]++; 
            sum[index] += x;
            w[index][pos[index]] = x;
        }
        printf("%d\n" , solve());
    }
    return 0;
}