TV 게임 질문(DP 번들)

농부 존의 젖소들은 게임에 중독되었다.원래 FJ는 도 교수의 방식대로 전기충격 중독을 없애려고 했지만 나중에 젖소들이 게임을 한 후에 원래보다 더 많은 젖을 낳는 것을 발견했다.만족하는 소가 젖을 더 많이 낳기 때문이라는 것은 분명하다.
그러나 젖소들은 어느 것이 가장 좋은 게임 플랫폼인지에 대해 큰 차이를 보였다.젖소 한 마리가 엑스박스 360을 사서 광기3를 뛰고 싶어 한다.또 한 마리의 젖소가 닌텐도 와이 한 대를 가지고'닌텐도 스타 대란투 X'를 뛰고 싶어한다.세 번째 젖소는 플레이스테이션3 위에서'잠룡첩보4'를 즐기고 싶은데, 고화질의 일본 영화도 볼 수 있다.FJ는 주어진 예산 내에 게임 플랫폼과 게임을 구입하여 그의 젖소들이 가장 많은 젖소를 생산하여 가장 많은 아이를 키우도록 하려고 한다.
FJ는 N(1<=N<=50)종의 게임 플랫폼을 연구했는데 각 게임 플랫폼의 가격은 Pi(1 <=P i <=1000) 및 각 게임 플랫폼에 G이 플랫폼에서만 실행할 수 있는 게임 i(1 <= G i <= 10)개.
젖소는 반드시 먼저 게임 플랫폼을 사야만 이런 게임 플랫폼에서 실행되는 게임을 살 수 있다는 것이 분명하다.한 게임당 한 게임의 가격 GPi(1 <=GP j 가격<=100) 및 하나의 산출치 PVj(1<=PV j<=1000000)는 소 한 마리가 이 게임을 한 후에 얼마나 많은 우유를 생산하는지 나타낸다.마지막으로 농부 존의 예산은 그가 가장 많이 쓸 수 있는 돈인 V(1<=V<=100000)이다.그가 얻을 수 있는 생산액과 최대치를 얻을 수 있도록 어떤 게임 플랫폼과 게임을 사야 하는지 확인해 주세요.
아래의 데이터를 고려하면 N종의 게임 플랫폼이 있고 V=800달러의 예산이 있다.첫 번째 게임 플랫폼은 300달러를 쓰고 두 개의 게임이 있는데 가격은 각각 30달러와 25달러이다. 그들의 생산치는 다음과 같다.
게임#소비 산출치
1 $30 50
2 $25 80
두 번째 플랫폼의 가격은 600달러이며 게임은 하나뿐입니다.
게임#소비 산출치
1 $50 130
세 번째 플랫폼의 가격은 400달러이며 세 가지 게임이 있습니다.
게임#소비 산출치
1 $40 70
2 $30 40
3 $35 60
농부 존은 제1과 제3의 플랫폼을 사고 플랫폼 1의 게임 2, 그리고 플랫폼 3의 게임 1과 게임 3을 사야 한다.결국 그의 마지막 산출치가 210:
산출치
예산: 800달러
플랫폼 1-$300
게임 2 -$25 80
플랫폼 3-400달러
게임 1-$40 70
게임 3 -$35 60
-------------------------------------------
합계: 0(>=0)210
입력
*첫 번째 줄: 공백으로 구분된 두 정수: N과 V
*제2~제N+1줄: i+1줄은 제i종 게임 플랫폼의 가격과 이런 게임 플랫폼에서 실행할 수 있는 게임을 나타낸다.포함:Pi, G_i 그리고 Gi 쌍이 공백으로 분리된 정수 GPj, PV_j
출력
*제1행: 농부 존이 예산에서 얻을 수 있는 가장 큰 생산액.
샘플 입력
3 800
300 2 30 50 25 80
600 1 50 130
400 3 40 70 30 40 35 60
샘플 출력
210
[사고방식] 각 플랫폼에 따라 모두 분류하고 이항식의 정리로 각 플랫폼에는 1024가지 분법이 있고 복잡도가 초과될 수 있음을 알 수 있다.
매번 한 플랫폼에 들어갈 때마다 먼저 이 플랫폼을 구매한 다음에 그 중의 게임에 대해 01DP를 한다. 이 플랫폼을 구매하지 않는 상황이 우수하지 않을 수 있기 때문에 물러날 때 원래의 판단과 함께 가장 좋은 것을 취한다.
【코드】

#include 
#include 
#include 
#include 
using namespace std;
int n,v,f[55][100005],mon,num,x,y;
int main(){
    scanf("%d%d",&n,&v);
    memset(f,0,sizeof(f));
    for(int i=1;i<=n;++i){
        scanf("%d%d",&mon,&num);
        for(int j=mon;j<=v;++j)f[i][j]=f[i-1][j-mon];
        for(int j=1;j<=num;++j){
            scanf("%d%d",&x,&y);
            for(int k=v;k>=(x+mon);--k)f[i][k]=max(f[i][k],f[i][k-x]+y);
		}
		for(int j=0;j<=v;++j)f[i][j]=max(f[i][j],f[i-1][j]);
	}
	printf("%d
",f[n][v]);
	return 0;
}