http://www.vijos.cn/Problem_Show.asp?id=1317
#include<iostream>
using namespace std;
int dp[30001];//dp[i]背包容量為i時(shí)從1……x個(gè)物品中選取的最優(yōu)值
int MAX(int x,int y)
{
    if(x>y)
        return x;
    else
        return y;
}
int main()
{
    int c,m;//c總共錢數(shù)，m物品數(shù)
    while(cin>>c>>m)
    {
        int i,j;
        int v[25],p[25];//v[i]、p[i]分別表示第 i 件物品的價(jià)格和重要度
        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;
}