很容易看出来是一个背包问题，开始把每一张钞票都跑了一遍01背包，直接TLE了。
其实就是多重背包模板题。
1 //#include <bits/stdc++.h> 2 #include <iostream> 3 #include <utility> 4 #include <vector> 5 #include <cstring> 6 using namespace std; 7 #define fst first 8 #define scd second 9 #define pb(x) push_back((x)) 10 #define mkp(x,y) make_pair((x),(y)) 11 #define ist(x) insert((x)) 12 typedef long long ll; 13 typedef pair<int ,int > pii; 14 typedef pair<ll ,ll > pll; 15 typedef vector< int > vi; 16 ll gcd(ll a,ll b){ return b==0?a:gcd(b,a%b);} 17 ll qPow(ll a,ll b,ll mod){ ll ret=1ll;while(b){ if(b&1) ret=ret*a%mod;a=a*a%mod;b>>=1;} return ret; } 18 19 pii nD[13]; 20 int dp[100000+5]; 21 int nValue; 22 23 void ZeroOnePack(int cost , int weight){ 24 for(int i=nValue;i>=cost;i--) 25 dp[i]=max(dp[i],dp[i-cost]+weight); 26 } 27 28 void CompletePack(int cost , int weight){ 29 for(int i=cost;i<=nValue;++i) 30 dp[i]=max(dp[i],dp[i-cost]+weight); 31 } 32 33 void MultiplePack(int cost ,int weight,int amount){ 34 if(cost*amount>=nValue) CompletePack(cost , weight); 35 else{ 36 int k=1; 37 while(k<amount){ 38 ZeroOnePack(k*cost,k*weight); 39 amount-=k; 40 k<<=1; 41 } 42 ZeroOnePack(amount*cost,amount*weight); 43 } 44 } 45 46 int main(){ 47 int cash,N; 48 while(cin>>cash>>N){ 49 nValue=cash; 50 memset(dp,0,sizeof(dp)); 51 for(int i=0;i<N;++i) 52 cin>>nD[i].first>>nD[i].second; 53 for(int i=0;i<N;++i){ 54 MultiplePack(nD[i].second,nD[i].second,nD[i].first); 55 } 56 cout<<dp[cash]<<endl; 57 } 58 return 0; 59 }