摸索C語言 前身 : 摸索C語言 http://mypaper.pchome.com.tw/iustlovefish 現在即將就讀中興大學資訊科學與工程學系 XD

79愛的鼓勵 1訂閱站台

DP(背包問題)

/************************************************************/

#include<stdio.h>                 
#include<stdlib.h>     
main()     
{     
 int n,a,b,m;  
 while(scanf("%d %d",&n,&m)==2)  
  {  
   int value[50000]={0},max=0,sum=n*m;  
   for(a=0;a<m;a++)  
    {  
     int w1,w,price1;  
     scanf("%d %d",&w1,&price1);
     for(b=n-w1;b>=0;b--) 
      {  
       if(value[b+w1]<value[b]+price1*w1)
        {  
         value[b+w1]=value[b]+price1*w1;  
         if(value[b+w1]>max)  
          max=value[b+w1];  
        }  
      }
    }  
    printf("%d\n",max);  
  }  
 return 0;     
}