题目：传送门 分析：简单多重背包问题，第一次做此类型问题，看了dd大牛的《背包问题九讲》做的。不得不说这些大牛是真的厉害啊，高中时期就能写出如此清晰透彻的讲解。 代码：
#include <iostream> #include <algorithm> #include <cstring> #include <string> using namespace std; const int MAXV=1e5+5; const int MAXN=12; int n; int dp[MAXV]; int m[MAXN],w[MAXN],c[MAXN]; int v; void zeroOnePack(int w,int c){ for(int i=v;i>=c;--i){ dp[i]=max(dp[i],dp[i-c]+w); } } void completePack(int w,int c){ for(int i=c;i<=v;++i){ dp[i]=max(dp[i],dp[i-c]+w); } } void multiPack(int w,int c,int m){ if(c*m>=v) completePack(w,c); else{ int k=1; while(k<m){ zeroOnePack(k*w,k*c); m-=k; k<<=1; } zeroOnePack(m*w,m*c); } } int main(){ ios::sync_with_stdio(false); int cash; while(cin>>cash>>n){ v=cash; for(int i=0;i<n;++i){ cin>>m[i]>>w[i]; c[i]=w[i]; } memset(dp,0,sizeof dp); if((!v)||(!n)) cout<<0<<endl; else{ for(int i=0;i<n;++i){ multiPack(w[i],c[i],m[i]); } cout<<dp[v]<<endl; } } return 0; }