dp之分组背包hdu3535（推荐）

题意：有0,1,2三种任务，0任务中的任务至少得完成一件，1中的任务最多完成1件，2中的任务随便做。每一个任务最多只能做一次 。n代表有n组任务，t代表有t分钟，m代表这组任务有m个子任务，s代表这m个子任务属于0,1,2中的哪种类型，接下来是m个子任务，第一个数代表要花费的时间，第二个数代表得到的愉悦度......求在可以完成工作的情况的最大愉悦度....要是不能完成，输出-1(题意要求每个子任务只能被取一次)

错误思路：我一开始想，把0，1，2这三大组任务的子任务先统计好，在dp的时候，我开dp[3][105],代表在完成3组任务体积为105的情况的最大愉悦度.......这种思路是错的，因为题目给出的n组任务是有其固定顺序，只能是按照它给出来的解决问题.......

ac思路：分为n组，每一组判断这一组是属于0,1,2三种任务中的哪一组......

若是属于0，那么将这一组的dp[i][j],j从0~~t全部置为负无穷大，然后开始动态转移.....为什么要置为负无穷大？因为只有这样才能不出现一个都不选择的情况.....其动态转移方程，，在我前一个分组背包题目已经详细推导过，就是dp[i][j]=max(dp[i][j-v[i]]+val[i],dp[i-1][j-v[i]]+val[i],dp[i][j])

若是属于1，先将第i-1的状态传递到第i状态，在开始分组背包的模板......最多取一个dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+val[i]);

若是属于2，先将第i-1的状态传递到第i状态,随意取，那么可以不取，取任意个子任务......dp[i][j]=max(dp[i-1][j],dp[i][j-v[i]]+val[i],dp[i-1][j-v[i]]+val[i]);

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
#define M -1000000000
int dp[105][105],s[105][2];
int main()
{
    int n,t;
    while(scanf("%d %d",&n,&t)>0)
    {
        int m,k;
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;i++)
        {
            scanf("%d %d",&m,&k);
            for(int j=1;j<=m;j++)
            scanf("%d %d",&s[j][0],&s[j][1]);
            if(k!=0)
            for(int j=0;j<=t;j++)        // 传递状态 
            dp[i][j]=dp[i-1][j];
            if(k==0)                        //至少取一个 ，分组背包变形模板....... 
            {
                for(int tmp=0;tmp<=t;tmp++) 
                dp[i][tmp]=M;
                for(int tmp=1;tmp<=m;tmp++)  //这层for循环必须在前面...... 
                {
                    for(int j=t;j>=0;j--)             
                    {
                        if(j-s[tmp][0]>=0&&dp[i][j-s[tmp][0]]+s[tmp][1]>dp[i][j])
                        dp[i][j]=dp[i][j-s[tmp][0]]+s[tmp][1];
                        
                        if(j-s[tmp][0]>=0&&dp[i-1][j-s[tmp][0]]+s[tmp][1]>dp[i][j])
                        dp[i][j]=dp[i-1][j-s[tmp][0]]+s[tmp][1];
                    }
                }
            }
            else if(k==1)               //最多取一个 ，分组背包模板 
            {
                for(int j=t;j>=0;j--)
                {
                    for(int tmp=1;tmp<=m;tmp++)
                    {    
                        if(j-s[tmp][0]>=0)
                        {
                            if(dp[i-1][j-s[tmp][0]]+s[tmp][1]>dp[i][j])
                            dp[i][j]=dp[i-1][j-s[tmp][0]]+s[tmp][1];
                        }    
                    }
                }
            }
            else if(k==2)                     //随意取 ，01背包，每个子任务只能取一次，却可以取任意个不同的子任务 
            {
                for(int tmp=1;tmp<=m;tmp++)
                {
                    for(int j=t;j>=s[tmp][0];j--)
                    {
                        if(dp[i][j-s[tmp][0]]+s[tmp][1]>dp[i][j])
                        dp[i][j]=dp[i][j-s[tmp][0]]+s[tmp][1];
                        
                        if(dp[i-1][j-s[tmp][0]]+s[tmp][1]>dp[i][j])
                        dp[i][j]=dp[i-1][j-s[tmp][0]]+s[tmp][1];

                    }
                }
            }
        }
        if(dp[n][t]<0)
        printf("-1
");
        else
        printf("%d
",dp[n][t]);
    }
    return 0;
}