[C++知识库]【C系列综合1】游戏达人I

Description

ACM队的ydw是个游戏的狂热爱好者，他喜好玩各种各样的单机游戏，以可以得到各种不同的结局通关为乐，但是由于时间有限（他还要出题TAT），于是他只能选择自己喜欢的几个结局来通关，由于ydw是游戏达人，因此他可以自己搞定所有的剧情而不去查攻略，但是由于自力更生，完成每个结局的时间是不同的，而他对每一个结局的喜好度也是不同的，即通关每个结局他获得的愉悦度是不同的。他希望在自己有限的时间内可以通关某些结局来使得自己的愉悦度最大。

Input

有多组测试数据，

第1行为N（0<N<=100）和T(0<T<=2000)，表示ydw有N个游戏可以玩，玩游戏的总的时间为T。

接下来3*N行，每行第一个数字n(1<=n<=10)表示这个游戏有几种结局，接下来的一行n个数字表示通关某个结局ydw可以获得的愉悦度，再接下来一行的n个数字表示ydw通关某个结局需要的时间。

测试数据以0 0结尾。（数据保证愉悦度和时间均大于0，小于等于1000）

Output

ydw可以获得的最大愉悦度。

Samples

input?Copy

1 10

2

3 5

4 6

1 9

2

3 5

4 6

0 0

output?Copy

8 5

Hint

第1组数据中，ydw有10的时间去玩1个游戏，2个结局分别耗时为4和6，而愉悦度为3和5，刚好可以达到，则愉悦度为8。

第2组中，时间为9，只能玩1个结局，则最大为5。

//代码ac了的

#include <stdio.h>
/*struct beibao
{
?? ?int n;
?? ?int w[1000];
?? ?int v[1000];
};*/
int w[1000]={0};
int v[1000]={0};
int f[1001][2001];
void print(int w[],int n);
void qk(int w[],int v[],int f[][2001],int j,int l,int t)
{
?? ?for(int i=0;i<j;++i)
?? ?{
?? ??? ?v[i]=0;
?? ?}
?? ?for(int i=0;i<l;++i)
?? ?{
?? ??? ?w[i]=0;
?? ?}
?? ?for(int i=1;i<j;++i)
?? ?{
?? ??? ?for(int k=1;k<=t;++k)
?? ??? ?{
?? ??? ??? ?f[i][k]=0;
?? ??? ?}
?? ?}
}
int main(void)
{
?? ?//struct beibao p[100];
?? ?int nn,n,t,j=0,l=0;
?? ?while(scanf("%d %d",&nn,&t)!=EOF)
?? ?{
?? ??? ?if(nn==0&&t==0) break;
?? ??? ?j=1;
?? ??? ?l=1;
?? ??? ?while(nn--)
?? ??? ?{
?? ??? ??? ?scanf("%d",&n);
?? ??? ??? ?for(int i=0;i<n;++i)
?? ??? ??? ?{
?? ??? ??? ??? ?scanf("%d",&v[j]);
?? ??? ??? ??? ?j++;
?? ??? ??? ?}
?? ??? ??? ?for(int i=0;i<n;++i)
?? ??? ??? ?{
?? ??? ??? ??? ?scanf("%d",&w[l]);
?? ??? ??? ??? ?l++;
?? ??? ??? ?}
?? ??? ?}
?? ??? ?for(int i=1;i<j;++i)
?? ??? ?{
?? ??? ??? ?for(int k=1;k<=t;++k)
?? ??? ??? ?{
?? ??? ??? ??? ?if(w[i]>k)
?? ??? ??? ??? ??? ?f[i][k]=f[i-1][k];
?? ??? ??? ??? ?else
?? ??? ??? ??? ??? ?f[i][k]=f[i-1][k]>f[i-1][k-w[i]]+v[i]?f[i-1][k]:f[i-1][k-w[i]]+v[i];?? ?
?? ??? ??? ?}
?? ??? ?}
?? ?/*?? ?for(int i=0;i<j;++i)
?? ??? ?{
?? ??? ?for(int k=0;k<=t;++k)
?? ??? ??? ?printf("f[%d][%d]=%d\n",i,j,f[i][k]);
?? ??? ?}*/
?? ??? ?printf("%d\n",f[j-1][t]);
?? ?//?? ?print(v,n);
?? ?//?? ?printf("%d %d",j,l);
?? ?//?? ?printf("%d\n",n);
?? ??? ?qk(w,v,f,j,l,t);
?? ?}
?? ?return 0;
}
//void qk(int w[],int v[],int f[][2000],int j,int l,int t)
//本题属于01背包动态规划类，就是要定义两个一维数组，再加一个二维数组，然后一串核心代码，但是要注意下标，下标是从1开始的，最大或是最小的那个输出的下标是分别两个的最大处，为什么下星期再说，我自己都不懂，加油