分组背包神马的...

分组背包神马的...

Problem Description

allen有n种苹果，要将它放入容量为v的背包。而allen厌烦吃同一种苹果，所以每种至多只能放一个。给出第i种中第j个苹果的大小和价钱，求出能放入背包的苹果的总价钱最大值。

Input

有多组测试数据，每组测试数据第一行为2个正整数，分别代表苹果的个数n和背包的容量v，n、v同时为0时结束测试，此时不输出。接下来有n个小组。每个小组的第一行为1个正整数，代表该种苹果的个数m。接下来有m行，每行有2个整数，用空格隔开，分别代表每个苹果的大小c和价钱w。所有输入数字的范围大于等于0，小于等于100。

Output

对每组测试数据输出一个整数，代表能放入背包的苹果的总价值。

Sample Input

3 3

1 1 1

2

1 1

2 1

1

3 1

0 0

Sample Output

2

昨天听狐狸大大提起~~睡前的手机党时间就看了看~~分组背包还是很好理解的...就是多个01背包...比如当前一组的物品.都是通过前一个背好的包来更新当前的包..注意..这些物品都是通过前一个包来更新当前的包..所以相互之间是影响不到的..再一个..因为每次更新只与前一个背包相关..所以只需两个背包..滚动着使用就好了...

Program:

#includeusing namespace std;int n,v,dp[2][120],c,w,m,p,t,i,ans;bool can[120];int main(){ freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); while (~scanf("%d%d",&n,&v)) { if (!n && !v) break; t=0; memset(dp[0],0,sizeof(dp[0])); memset(can,false,sizeof(can)); can[0]=true; for (p=1;p<=n;p++) { scanf("%d",&m); t=1-t; for (i=0;i<=n;i++) dp[t][i]=dp[1-t][i]; while (m--) { scanf("%d%d",&c,&w); for (i=v-c;i>=0;i--) if (can[i] && dp[1-t][i]+w>dp[t][i+c]) { can[i+c]=true; dp[t][i+c]=dp[1-t][i]+w; } } } ans=0; for (i=0;i<=n;i++) if (dp[t][i]>ans) ans=dp[t][i]; printf("%d\n",ans); } return 0; }

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。