HDU 3732 Ahui Writes Word（多重背包问题）

Description
小明要学习背单词，一共有n个单词，每个单词有一个难度c和价值v，问小明所被单词总难度不超过V的情况下能够得到的最大价值
Input
第一行为两个整数n和V分别表示单词数量和难度上限，之后n行每行一个字符串表示该单词，之后两个整数v和c表示该单词的价值和难度
(1≤n≤100000,1≤V≤10000,0 ≤v,c≤10)
Output
输出在总难度不超过V的情况下所获的最大价值
Sample Input
5 20
go 5 8
think 3 7
big 7 4
read 2 6
write 3 5
Sample Output
15
Solution
n*V很大，完全背包会超时，而c和v的值比较小，所以可以用一个10*10的矩阵cnt表示一种物品，cnt[i][j]表示价值为i难度为j的物品数量，问题转化为多重背包
Code

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
#define maxn 11111
int dp[maxn],v,n,cnt[11][11];
void Complete_Pack(int cost,int weight)//完全背包 
{
for(int i=cost;i<=v;i++)
        dp[i]=max(dp[i],dp[i-cost]+weight);     
}
void ZeroOne_Pack(int cost,int weight)//01背包 
{
for(int i=v;i>=cost;i--)
        dp[i]=max(dp[i],dp[i-cost]+weight);
}
void Multiple_Pack(int cost,int weight,int amount)//多重背包 
{
if(cost*amount>=v)
    {
        Complete_Pack(cost,weight);
return;
    }
int k=1;
while(k<amount)
    {
        ZeroOne_Pack(k*cost,k*weight);
        amount-=k;
        k*=2;
    }
    ZeroOne_Pack(amount*cost,amount*weight);
}
int main()
{
while(~scanf("%d%d",&n,&v))
    {
char s[111];
memset(cnt,0,sizeof(cnt));
memset(dp,0,sizeof(dp));
for(int i=0;i<n;i++)
        {
int a,b;
scanf("%s%d%d",s,&a,&b);
            cnt[b][a]++;
        }
for(int i=0;i<11;i++)
for(int j=0;j<11;j++)
if(cnt[i][j])
                    Multiple_Pack(i,j,cnt[i][j]);
printf("%d\n",dp[v]);
    }
return 0;
}