题意：

有n件物品，每件物品有体积$v_i$和价值$w_i$，问体积为m的背包最多可以装下多大价值的物品。其中$n \leq 100$ ，其他数据均匀随机并且不超过$10^9$。

思路：

很典型的背包问题，然而背包的大小变成了$10^9$，最简单的01背包的做法不行，交换两维状态（前i件物品价值为j占用的最小体积）的做法也不行。$n \leq 100$，折半枚举也不行。

那怎么办呢？所以看了题解…

这又是数据随机下的玄学做法。因为数据均匀随机，所以事实上状态数是很少的。所以把状态放进容器，每次dp的时候遍历一下。这里有些状态是可以删掉的，如果价值小花费的体积反而多，就可以删掉。所以根据价值从大到小排序，然后把这些状态删去就好了。

这里还有一个搜索+剪枝的做法，不知是数据水还是什么原因，剪枝就是按性价比排序，然后进行后缀优化，如果背包全部放当前性价比的东西价值却没有超过当前的最大值就剪掉，当然体积如果大于m也剪掉。

代码：

typedef long long ll;
struct node
{
    ll cost,val;
}a[110];
bool cmp(pair<ll,ll> x,pair<ll,ll> y)
{
    if(x.second!=y.second)return x.second>y.second;
    return x.first<y.first;
}
int main()
{
    int n;
    ll m;
    while(scanf("%d%lld",&n,&m)!=EOF)
    {
        vector<pair<ll,ll> >v[110];//cost,val
        for(int i=1;i<=n;i++)
            scanf("%lld%lld",&a[i].cost,&a[i].val);
        pair<ll,ll>p;
        p.first=0;p.first=0;
        v[0].push_back(p);
        for(int i=1;i<=n;i++)
        {
            int len=v[i-1].size();
            for(int j=0;j<len;j++)
            {
                v[i].push_back(v[i-1][j]);
                p=v[i-1][j];
                if(p.first+a[i].cost<=m)
                {
                    p.first+=a[i].cost;p.second+=a[i].val;
                    v[i].push_back(p);
                }
            }
            sort(v[i].begin(),v[i].end(),cmp);//把时间多价值却小的删掉
            int ls=0;
            for(int j=1;j<v[i].size();j++)
            {
                if(v[i][j].first>=v[i][ls].first)
                    v[i].erase(v[i].begin()+j);
                else ls=j;
            }
            /*for(int j=0;j<v[i].size();j++)
                printf("(%lld,%lld)",v[i][j].first,v[i][j].second);
            printf("\n");*/
        }
        printf("%lld\n",v[n][0].second);
    }
    return 0;
}