735 3 4 125 6 5 3 350//735的最大额，3种，4个125,6个5,3个350633 4 500 30 6 100 1 5 0 1735 00 3 10 100 10 50 10 10
73563000
1 #include<cstdio> 2 #include<iostream> 3 #include<algorithm> 4 #include<cstring> 5 #include<cmath> 6 #include<queue> 7 using namespace std; 8 const int maxn=100005; 9 int n,m,t;10 int dp[maxn],w[maxn],v[maxn];11 int nValue;12 //0-1背包，代价为cost,获得的价值为weight13 void ZeroOnePack(int cost,int weight)14 {15for(int i=nValue;i>=cost;i--)16 dp[i]=max(dp[i],dp[i-cost]+weight);17 }18 19 //完全背包，代价为cost,获得的价值为weight20 void CompletePack(int cost,int weight)21 {22for(int i=cost;i<=nValue;i++)23 dp[i]=max(dp[i],dp[i-cost]+weight);24 }25 26 //多重背包27 void MultiplePack(int cost,int weight,int amount)28 {29if(cost*amount>=nValue) CompletePack(cost,weight);30else31{32 int k=1;33 while(k<amount)34 {35 ZeroOnePack(k*cost,k*weight);36 amount-=k;37 k<<=1;38 }39 ZeroOnePack(amount*cost,amount*weight);//这个不要忘记了，经常掉了40}41 }42 int main()43 {44int i,j,k;45#ifndef ONLINE_JUDGE46freopen("1.in","r",stdin);47#endif48while(scanf("%d%d",&nValue,&n)!=EOF)49{50 for(i=0;i<n;i++)51 {52 scanf("%d%d",&w[i],&v[i]);53 }54 memset(dp,0,sizeof(dp));55 for(i=0;i<n;i++)56 {57 MultiplePack(v[i],v[i],w[i]);58 }59 printf("%d\n",dp[nValue]);60}61 }
