http://www.vijos.cn/Problem_Show.asp?id=1317
#include<iostream>
using namespace std;
int dp[30001];//dp[i]背包容量为i时从1……x个物品中选取的最优值
int MAX(int x,int y)
{
    
if(x>y)
        
return x;
    
else
        
return y;
}

int main()
{
    
int c,m;//c总共钱数,m物品数
    while(cin>>c>>m)
    
{
        
int i,j;
        
int v[25],p[25];//v[i]、p[i]分别表示第 i 件物品的价格和重要度
        for(i=1;i<=m;i++)
            scanf(
"%d%d",&v[i],&p[i]);

        
for(j=0;j<v[1];j++)
            dp[j] 
= 0;
        
for(;j<=c;j++)
            dp[j] 
= v[1* p[1];

        
for(i=2;i<=m;i++)
        
{
            
for(j=c;j>=v[i];j--)
                dp[j] 
= MAX(dp[j],dp[j-v[i]] + v[i] * p[i]);
        }

        cout
<<dp[c]<<endl;
    }

    
return 0;
}