链接：http://218.28.19.228/cogs/problem/problem.php?pid=2230

题解：
论一类神兽的毒瘤数据和奇技淫巧题的解题技巧

朴素算法O（NM）妥妥要挂
但这道题考的是脑筋急转弯……
注意到v，w的数据范围特别小，也就是说所给出的物品中一定有许多是重复的
根据这个特点，可以类比计数排序的思路，用c[i][j]统计重量为i 价值为j的物品的个数，然后再把每个c[i][j]二进制拆分成单个物品，在进行01背包，就A了

只要能反应过来，这就是一道多重背包的裸题
然而出题人很心机orz

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define Nmax 40001
using namespace std;
int c[25][25];
int f[Nmax];
int w[Nmax],v[Nmax];
int cnt;
int main()
{
    freopen("crazytime.in","r",stdin);
    freopen("crazytime.out","w",stdout); 
    int n,m;
    scanf("%d%d",&n,&m);
    int aa,bb,ma=0,mb=0;
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&aa,&bb);
        c[aa][bb]++;
        ma=max(ma,aa);
        mb=max(mb,bb);
    }
    for(int i=1;i<=ma;i++)
        for(int j=1;j<=mb;j++)
        {
            int t=1;
            while(c[i][j]>=t)
            {
                c[i][j]-=t;
                w[++cnt]=t*i;
                v[cnt]=t*j;
                t<<=1;
            }
            if(c[i][j])
            {
                w[++cnt]=c[i][j]*i;
                v[cnt]=c[i][j]*j;
                c[i][j]=0;                  
            } 
        }
    for(int i=1;i<=cnt;i++)
        for(int j=m;j>=w[i];j--)
        f[j]=max(f[j],f[j-w[i]]+v[i]);
    printf("%d",f[m]);
    return 0;       
}