여행 가방 (다 차원 유 계 의 가방 문제)

     ？       ！

         ，   n (n<=50)    ，        vi，  wi，  ci，  ti (vi,wi,ci ti    )。
      V    (V<=1000)，    W  (W<=500)。

         ，            ，          ？

  ：
                              
    （    ）  （  ）   （ ）    （ ）
  1        30          3        10       4
  2        50          8        10       5
  3        10          2        10       2
  4        23          5        8        3
  5        130         20       5        11

 V 500，W 100，           72（ 72=10*4+10*2+4*3： 10   1，10   3， 4   4  ）。

              ，    0-1         。

    ：

   ，     n，       V，        W。n,V W       。
   n ，       i   vi，  wi，  ci，  ti (  vi,wi,ci ti    )。
  
    ：
  
   ，                。
  
    ：
  
5 500 100
30 3 10 4
50 8 10 5
10 2 10 2
23 5 8 3
130 20 5 11
  
    ：
  
72
  

  
  ：
  
         ，               ，             。
  

  
 n   ，      v[i]，  w[i]，c[i] ，  t[i]。
  
 ：m[i][x][y]      i    ，          x ,      y ，     。
  
           0；
  

  
        ：
  
  i=1  ：
  
m[1][x][y]=0                                      x<v[1]||y<w[1];
  
m[1][x][y]=min(x/v[1],y/[w[1],c[1])*t[1]          x>=v[1]&&y>=w[1];
  

  
  i>1  :
  
m[i][x][y]=max{m[i-1][x][y],m[i-1][x-k*v[i]][y-k*w[i]]+k*t[i]}      x>=v[i]&&y>=w[i];     :  0<k<min(x/v[i],y/w[i],c[i]);
  
m[i][x][y]=m[i-1][x][y]                                             x<v[i]||y<w[i];                     
  
k       i       ；
  
 
  
    ：
  

  
#include<iostream>
using namespace std;


int m[51][1001][501]={0};     //m[i][j][k]      i    ，      j，       k     
int v_arr[51];                //    
int w_arr[51];                //  
int c_arr[51];               //  
int t_arr[51];               //  



int min(int a,int b,int c){        //      
	int m;
	m=a;
	if(b<m)
		m=b;
	if(c<m)
		m=c;
	return m;
}


void func(int v,int w,int n){    //   n   ，     v，     w
      
     int i=0,j=0;
     int x=0,y=0;
	 int k=0,max=0;


    for(x=0;x<=v;x++)
		for(y=0;y<=w;y++)
			if((x/v_arr[1]>0)&&(y/w_arr[1]>0))                               //x>=v_arr[1]&&y>=w_arr[1]
				m[1][x][y]=min(x/v_arr[1],y/w_arr[1],c_arr[1])*t_arr[1];     //m[1][x][y]    
			else
				m[1][x][y]=0;                                                //x<v_arr[1]&&y<w_arr[1]                   


	for(i=2;i<=n;i++)                                             //  i=2    
		for(x=0;x<=v;x++)
			for(y=0;y<=w;y++){
				max=m[i-1][x][y];
				if((x>=v_arr[i])&&(y>=w_arr[i])){
				   for(k=0;k<=min(x/v_arr[i],y/w_arr[i],c_arr[i]);k++)
                     if((m[i-1][x-k*v_arr[i]][y-k*w_arr[i]]+k*t_arr[i])>max)         //        
						 max=(m[i-1][x-k*v_arr[i]][y-k*w_arr[i]]+k*t_arr[i]);
					 m[i][x][y]=max;
				}
                else
					m[i][x][y]=m[i-1][x][y];
			}

     }


int main(){
   int n=0;    //    
   int v=0;    //    
   int w=0;    //    
 

   cin>>n>>v>>w;
   
   for(int i=1;i<=n;i++)
       cin>>v_arr[i]>>w_arr[i]>>c_arr[i]>>t_arr[i];
       
   func(v, w, n);
   cout<<m[n][v][w];
   return 0;
}