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

79愛的鼓勵 1訂閱站台

DP(背包問題)解法，目前還不是很熟，只有使用模仿的方式
要問我我也不太懂，
/***********************************************************/

1. #include<stdio.h>   
2. #include<stdlib.h>   
3. main()   
4. {   
5.     
6.  int a,b,c,n,max;   
7.  while(scanf("%d %d",&max,&n)==2)   
8.  {   
9.   int value[1000]={0};   
10.   int w,price,maxprice=0;   
11.   for(a=0;a<n;a++)   
12.     {   
13.      scanf("%d %d",&w,&price);   
14.      for(b=max-w;b>=0;b--)   
15.       {   
16.        if(value[b+w]<value[b]+price)   
17.         {   
18.          value[b+w]=value[b]+price;   
19.          if(value[b+w]>maxprice)   
20.           maxprice=value[b+w];   
21.         }   
22.       }    
23.     }   
24.     printf("%d\n",maxprice);   
25.  }   
26.  return 0;   
27. }