学步园

背景：难！！不看解题报告是绝对想不到。即使看了解题报告的思路再去裸写也有很多误区。。。。真是对思维有很大提升。

思路：用一个二维数组F[i][j]来表示取第i个分组时，背包容量为j所能获得的最大快乐值。

         对于s==0（至少取一个的情况），先把F[i]的值全部设为-INF，这样是为了保证至少选一个。转移方程:F[i][j]=max{F[i][j],max{F[i-1][j-cost[k]+weight[k],F[i][j-cost[k]]+weight[k]}}。当F[i][j-cost[k]]为-INF的时候，这个状态就还没有选背包，显然F[i-1][j-cost[k]]会比它大，就是还没有选背包的时候，一定会选一个。这样保证，对于每一个至少选一个的分组，只有它已经至少选了一个该分组内的背包，才能使状态内值为正值。对于这个分组的下一个分组，也只能用上面的非负值数据，这样就完美的保证了，对于每一个至少选择一个的分组都至少选择了一个。

        对于s==1至多选择一个，先把上一组的数据复制到当前组来，因为里面很可能还要很多-INF的值需要代代相传，才能保证那些至少选一个的组有所选择。总是把F[i][j]更新为在上一组的基础上，选择一个物品的最大值。

       对于s==0任意选，依然先把上一组的数据复制到当前组来，然后01背包。

学习：1.注意把物品循环和限制循环交换只有完全背包，不要太想当然了。

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int F[109][109],n,v,cost[109],weight[109],ith;

void free(void){    //make the zeroonebag choose to each thing.
     for(int i=0;i < n;i++)
        for(int j=v;j >= cost[i];j--)
            F[ith][j]=max(F[ith-1][j-cost[i]]+weight[i],max(F[ith][j],F[ith][j-cost[i]]+weight[i]));
}

void atmost1(void){    //like the easy breakteambag.
         for(int j=0;j < n;j++)
             for(int i=v;i >= cost[j];i--)
                 F[ith][i]=max(F[ith][i],F[ith-1][i-cost[j]]+weight[j]);
}

int atleast1(void){
    bool ok=true;
    for(int i=0;i < n;i++) if(cost[i] <= v){ok=false;}
    if(ok) return 0;    //don't satisfy the requirement of boss.
    for(int i=0;i < n;i++){
        for(int j=v;j >= cost[i];j--){
            F[ith][j]=max(F[ith][j],max(F[ith-1][j-cost[i]]+weight[i],F[ith][j-cost[i]]+weight[i]));
        }
    }
    return 1;
}

int main(void){
    int t;
    while(~scanf("%d%d",&t,&v)){
        bool flag=true;
        memset(F,0,sizeof(F));
        for(ith=1;ith <= t;ith++){
            int s;
            scanf("%d%d",&n,&s);
            for(int i=0;i < n;i++) scanf("%d%d",&cost[i],&weight[i]);
            if(s == 1) atmost1();
            else if(s == 2) free();
            else{
                for(int i=0;i <= v;i++) F[ith][i]=-100000000;
                if(atleast1() == 0 && flag){printf("-1\n");flag=false;}
            }
            for(int i=0;i <= v;i++) F[ith+1][i]=F[ith][i];
        }
        if(flag){

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