POJ - 1276 Cash Machine(多重背包)
时间:2022-04-03 14:21
题意
给一个最大额度cash,现有N种面值的纸币,第i种纸币有ni张,价值为Di。问用这些纸币能凑出来的最大金额数,要求不超过cash。
分析
多重背包问题。这里的Di即是价值也是花费。模板题
#include<iostream> #include<cmath> #include<cstring> #include<queue> #include<vector> #include<cstdio> #include<algorithm> #include<map> #include<set> #define rep(i,e) for(int i=0;i<(e);i++) #define rep1(i,e) for(int i=1;i<=(e);i++) #define repx(i,x,e) for(int i=(x);i<=(e);i++) #define X first #define Y second #define PB push_back #define MP make_pair #define mset(var,val) memset(var,val,sizeof(var)) #define scd(a) scanf("%d",&a) #define scdd(a,b) scanf("%d%d",&a,&b) #define scddd(a,b,c) scanf("%d%d%d",&a,&b,&c) #define pd(a) printf("%d\n",a) #define scl(a) scanf("%lld",&a) #define scll(a,b) scanf("%lld%lld",&a,&b) #define sclll(a,b,c) scanf("%lld%lld%lld",&a,&b,&c) #define IOS ios::sync_with_stdio(false);cin.tie(0) using namespace std; typedef long long ll; template <class T> void test(T a){cout<<a<<endl;} template <class T,class T2> void test(T a,T2 b){cout<<a<<" "<<b<<endl;} template <class T,class T2,class T3> void test(T a,T2 b,T3 c){cout<<a<<" "<<b<<" "<<c<<endl;} template <class T> inline bool scan_d(T &ret){ char c;int sgn; if(c=getchar(),c==EOF) return 0; while(c!=‘-‘&&(c<‘0‘||c>‘9‘)) c=getchar(); sgn=(c==‘-‘)?-1:1; ret=(c==‘-‘)?0:(c-‘0‘); while(c=getchar(),c>=‘0‘&&c<=‘9‘) ret = ret*10+(c-‘0‘); ret*=sgn; return 1; } //const int N = 1e6+10; const int inf = 0x3f3f3f3f; const ll INF = 0x3f3f3f3f3f3f3f3fll; const ll mod = 1000000000; int T; void testcase(){ printf("Case %d:",++T); } const int MAXN = 5e5+10 ; const int MAXM = 250; const double eps = 1e-8; const double PI = acos(-1.0); int N,V; int dp[100005]; int n[15],d[15]; void ZeroOnePack(int c,int w){ for(int i=V;i>=c;i--){ dp[i]=max(dp[i],dp[i-c]+w); } } void CompletePack(int c,int w){ for(int i=c;i<=V;i++){ dp[i]=max(dp[i],dp[i-c]+w); } } void MultiplePack(int c,int w,int m){ if(c*m>=V){ CompletePack(c,w); }else{ int k=1; while(k<m){ ZeroOnePack(k*c,k*w); m=m-k; k<<=1; } ZeroOnePack(m*c,m*w); } } int main() { #ifdef LOCAL freopen("in.txt","r",stdin); #endif // LOCAL while(~scanf("%d",&V)){ scanf("%d",&N); for(int i=1;i<=N;i++){ scanf("%d%d",&n[i],&d[i]); } if(N==0 || V==0){ puts("0"); continue; } mset(dp,0); for(int i=1;i<=N;i++){ MultiplePack(d[i],d[i],n[i]); } cout<<dp[V]<<endl; } return 0; }