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

79愛的鼓勵 1訂閱站台

DP(背包問題) 我不熟，模仿而已

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

1. #include<stdio.h>                  
2. #include<stdlib.h>      
3. main()      
4. {      
5.  int n,a,b;   
6.  while(scanf("%d",&n)==1)   
7.   {   
8.    int value[200]={0},max=0;   
9.    /*學習中...*/ /*先設定101格 分別為0kg.1....到100*/  
10.    for(a=0;a<n;a++)   
11.     {   
12.      int w1,price1;   
13.      scanf("%d %d",&w1,&price1);   
14.      for(b=100-w1;b>=0;b--)           /*逼近最佳解*/    
15.       {   
16.        if(value[b+w1]<value[b]+price1)/*如果可以的話 就把那格往上加*/    
17.         {   
18.          value[b+w1]=value[b]+price1;   
19.          if(value[b+w1]>max)   
20.           max=value[b+w1];   
21.         }   
22.       }     
23.     }   
24.     printf("%d\n",max);   
25.   }   
26.  return 0;      
27. }   
28. /*動態規劃DP */  
29. /*http://caterpillar.onlyfun.net/Gossip/AlgorithmGossip/KnapsackProblem.htm*/