1 //Accepted    1100 KB    47 ms 2 //多重背包 3 #include <cstdio> 4 #include <cstring> 5 #include <iostream> 6 #include <queue> 7 #include <cmath> 8 #include <algorithm> 9 using namespace std;10 /**11   * This is a documentation comment block12   * 如果有一天你坚持不下去了，就想想你为什么走到这儿！13   * @authr songt14   */15 const int imax_v = 100005;16 const int imax_n = 15;17 int dp[imax_v];18 int weight[imax_n],amount[imax_n];19 int n,v;20 int max(int a,int b)21 {22     return a>b?a:b;23 }24 void zeroOnePack(int weight,int value,int v)25 {26     for (int j=v;j>=weight;j--)27     dp[j]=max(dp[j],dp[j-weight]+value);28 }29 void completePack(int weight,int value,int v)30 {31     for (int j=weight;j<=v;j++)32     dp[j]=max(dp[j],dp[j-weight]+value);33 }34 void multiplePack(int weight,int value,int amount,int v)35 {36     int k=1;37     if (amount*weight>=v)38     {39         completePack(weight,value,v);40         return ;41     }42     while (k<amount)43     {44         zeroOnePack(k*weight,k*value,v);45         amount-=k;46         k<<=1;47     }48     zeroOnePack(amount*weight,amount*value,v);49 }50 void Dp()51 {52     for (int i=1;i<=v;i++) dp[i]=0;53     for (int i=1;i<=n;i++)54     {55         multiplePack(weight[i],weight[i],amount[i],v);56     }57     int ans=0;58     for (int i=1;i<=v;i++)59     ans=max(ans,dp[i]);60     printf("%d\n",ans);61 }62 int main()63 {64     while (scanf("%d%d",&v,&n)!=EOF)65     {66         for (int i=1;i<=n;i++)67         scanf("%d%d",&amount[i],&weight[i]);68         Dp();69     }70     return 0;71 }