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}