hdu 3535 AreYouBusy 混合背包

題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=3535

題意：有三種任務，至少完成一個，至多完成一個，任意完成。現在給出k組任務，每組任務都屬於三種任務的一種。每個任務都會消耗時間，獲得幸福感。求時間T內的最大滿足感。

三種背包的混合。還是考察對背包問題的理解。顯然一維已經滿足不了要求了，我們設d[k][j]代表第k組容量為j時獲得的最大滿足感。

可以明顯比較出三種背包的區別。（任意取也就是01背包）

任意取，至少取一種的區別：只取一種的狀態是否非法。

任意取，至多取一種的區別：在當前組已取的情況下是否繼續取。

#include <iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define N 110
using namespace std;

int d[N][N];

int main()
{
    int n,m,s,T,c,w;
    while(~scanf("%d%d",&n,&T))
    {
        memset(d,0,sizeof(d));
        for(int k=1;k<=n;k++)
        {
            cin>>m>>s;
            for(int j=0;j<=T;j++)   d[k][j]=(s==0?-1:d[k-1][j]);
            //初始化第k組不取的狀態。s=0時非法，賦為-1。而其他合法，所以把狀態傳遞下去。
            for(int i=0;i<m;i++) s="=0)" int="" j="T;j">=c;j--)
                    {
                        if(d[k][j-c]!=-1)   d[k][j]=max(d[k][j],d[k][j-c]+w);
                        if(d[k-1][j-c]!=-1) d[k][j]=max(d[k][j],d[k-1][j-c]+w);//注意順序
                    }
                if(s==1)
                    for(int j=T;j>=c;j--)
                        if(d[k-1][j-c]!=-1)  d[k][j]=max(d[k][j],d[k-1][j-c]+w);
                if(s==2)
                    for(int j=T;j>=c;j--)
                    {
                        if(d[k][j-c]!=-1)    d[k][j]=max(d[k][j],d[k][j-c]+w);
                        if(d[k-1][j-c]!=-1)  d[k][j]=max(d[k][j],d[k-1][j-c]+w);
                    }
            }
        }
        cout<<d[n][t]<<endl; pre=""><p>
</p><p>
</p><p>
</p><p>
</p>
   
</d[n][t]<<endl;></m;i++)></cmath></cstring></cstdio></iostream>