Onway

前几天刚学0-1背包的时候就看过了这题，但没什么思路，今天算是学过了三种背包了，再看回这题，还是没什么思路。怎么人家都说是0-1背包呢，想了很久还是不知道怎么背包法，笨死。无奈看了discuss，豁然开朗。原来背包还可以这样玩，太有意思了。

题意：

有一堆衣服，多种颜色，每种颜色的可能有多件。有两个洗衣服速度相同的人要洗干净这堆衣服。每件衣服都有一个洗干净所要花费的时间。两个人同时工作，但只有一种颜色的衣服都洗完后，两人才可以开始洗其他颜色。问这两个人洗完这堆衣服最少需要多少时间。

思路：将某种颜色的时间之和的一半作为0-1背包的容量，物品的价值与重量等同于该种颜色的衣服所花费的时间，这是关键思路啊！只要求得这个背包的能获得的最大价值，就是说在这一半的时间里，有多少是被最有效利用的。然后总时间减去这个有效利用的，就是洗完这堆衣服最少要花费的时间。

要处理这个题的输入可能比较麻烦。将输入的数据转化为要进行背包的数据后，背包部分就简单了。

如果，这个题改一下，要分两行输出没人要洗的衣服呢？又怎么处理了？

 1#include <iostream>
 2#include <string>
 3#include <algorithm>
 4using namespace std;
 5const int MAX=50000;  //变成两个背包以后，一个的容量最多就是50000
 6char name[150];     //这个没什么用，就是吃掉那一行的名字输入
 7int sum[10];        //每一种颜色的时间之和
 8struct clother
 9{
10    int tim;
11    string color;
12}clo[100];
13int data[12][100];    //将原来读入的数据转化后好进行0-1背包
14int dp[10][MAX+1];    //不解析
15bool cmp(clother a,clother b)
16{return a.color<b.color;}
17
18int main()
19{
20    int m,n;
21    while(cin>>m>>n&&(n||m))
22    {
23        getchar();
24        cin.getline(name,150);
25        int i,j,k;
26        for(i=1;i<=n;++i)
27            cin>>clo[i].tim>>clo[i].color;
28        sort(clo+1,clo+1+n,cmp);         //输入完以后马上排序
29        
30        data[1][1]=clo[1].tim;
31        for(i=2,j=1,k=2;i<=n;++i)      //data[j][0]是记录第j种颜色的衣服件数
32            if(clo[i].color==clo[i-1].color)
33                data[j][k++]=clo[i].tim;
34            else
35            {
36                data[j][0]=--k;
37                ++j;
38                k=2;
39                data[j][1]=clo[i].tim;
40            }
41        data[j][0]=--k;
42        n=j;     //n变成了需要进行背包的颜色种数
43                //这一段很容易理解，但可能处理比较麻烦，从排序后的第二个数据，即i=2开始
44                //感觉这样比较好处理
45
46        memset(sum,0,sizeof(sum));   //这段是数据转化后进行时间之和统计
47        for(i=1;i<=n;++i)
48        {
49            for(j=1;j<=data[i][0];++j)
50                sum[i]+=data[i][j];
51        }
52
53        memset(dp,0,sizeof(dp));   //这一段就是进行0-1背包了
54        for(i=1;i<=n;++i)
55            for(j=1;j<=data[i][0];++j)
56                for(k=MAX;k>=data[i][j];--k)
57                    dp[i][k]=dp[i][k]>dp[i][k-data[i][j]]+data[i][j]?
58                    dp[i][k]:dp[i][k-data[i][j]]+data[i][j];
59
60        for(i=1;i<=n;++i)
61            sum[i]-=dp[i][sum[i]/2];  
62                //摘自poj discuss TangMing 的一句话：
63                //把sum[i]/2的背包最大填满,第i种颜色耗时就为 sum[i]-dp[sum[i]/2];
64                //虽然这段代码很短，但是整个思路的关键
65
66        for(i=1;i<=n;++i)
67            sum[0]+=sum[i];
68        cout<<sum[0]<<endl;
69    }
70    return 0;
71}