背景：难！！不看解题报告是绝对想不到。即使看了解题报告的思路再去裸写也有很多误区。。。。真是对思维有很大提升。
思路：用一个二维数组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;}
只要功夫深，铁棒磨成绣花针。
