hdu1864 01背包
题目大意：一堆数，找到一个最大的和满足这个和不超过Q
要学会分析复杂度！
#include <cstdio> #include <cstring> #define MAX(a,b) (a>b?a:b) const int N = 3000050; int dp[N],data[N]; float bound; int n,cnt; int main(){ char type; float price[3],tprice; while(scanf("%f%d",&bound,&n)&&n){ int totalCnt = 1; for(int i=0;i<n;i++){ scanf("%d",&cnt); bool flag = true; price[0]=price[1]=price[2]=0.0f; for(int j=0;j<cnt;j++){ getchar(); scanf("%c:%f",&type,&tprice); if((type!='A')&&(type!='B')&&(type!='C')) flag = false; else price[type-'A'] += tprice; } if(!flag) continue; if(price[0]>600||price[1]>600||price[2]>600) continue; float totalPrice = price[0]+price[1]+price[2]; if(totalPrice>1000) continue; data[totalCnt++] = (totalPrice*100); } memset(dp,0,sizeof(dp)); bound*=100; for(int i=1;i<totalCnt;i++) for(int v=bound;v>=data[i];v--) dp[v] = MAX(dp[v],dp[v-data[i]]+data[i]); printf("%.2f ",dp[bound]/100); } return 0; }
hdu2844 多重背包模板题
题目大意：两个数组A,C。表示有Ci个Ai，问1-m中有多少个数能由这堆数相加表示。
#include <set> #include <map> #include <stack> #include <queue> #include <cmath> #include <vector> #include <string> #include <cstdio> #include <cstring> #include <cstdlib> #include <iostream> #include <algorithm> #define MAX(a,b) ((a)>=(b)?(a):(b)) #define MIN(a,b) ((a)<=(b)?(a):(b)) #define OO 0x0fffffff using namespace std; const int N = 100100; int f[N],A[128],C[128]; int main(){ int n,m; int tcnt,tcv; while(scanf("%d%d",&n,&m),m+n){ memset(f,0,sizeof(f)); for(int i=0;i<n;i++) cin>>A[i]; for(int i=0;i<n;i++) cin>>C[i]; for(int i=0;i<n;i++){ tcnt = 1; while(C[i]){ tcv=tcnt*A[i]; for(int v=m;v>=tcv;v--) f[v] = MAX(f[v],f[v-tcv]+tcv); C[i]-=tcnt; if((tcnt<<1)<=C[i]) tcnt<<=1; else tcnt=C[i]; } } int ans = 0; for(int i=1;i<=m;i++) if(f[i]==i) ans++; printf("%d ",ans); } return 0; }
hdu2159 完全背包
最近xhd正在玩一款叫做FATE的游戏，为了得到极品装备，xhd在不停的杀怪做任务。久而久之xhd开始对杀怪产生的厌恶感，但又不得不通过杀怪来升完这最后一级。现在的问题是，xhd升掉最后一级还需n的经验值，xhd还留有m的忍耐度，每杀一个怪xhd会得到相应的经验，并减掉相应的忍耐度。当忍耐度降到0或者0以下时，xhd就不会玩这游戏。xhd还说了他最多只杀s只怪。请问他能升掉这最后一级吗？
/********************************************************/
二维费用的完全背包
#include <set> #include <map> #include <stack> #include <queue> #include <cmath> #include <vector> #include <string> #include <cstdio> #include <cstring> #include <cstdlib> #include <iostream> #include <algorithm> #define MAX(a,b) ((a)>=(b)?(a):(b)) #define MIN(a,b) ((a)<=(b)?(a):(b)) #define OO 0x0fffffff using namespace std; const int N = 128; int f[N][N],value[N],cost[N]; int main(){ int n,m,k,s; while(scanf("%d%d%d%d",&n,&m,&k,&s)!=EOF){ for(int i=0;i<k;i++) scanf("%d%d",value+i,cost+i); memset(f,0,sizeof(f)); for(int i=0;i<k;i++) for(int x=cost[i];x<=m;x++) for(int y=1;y<=s;y++){ f[x][y] = MAX(f[x][y],f[x-cost[i]][y-1]+value[i]); } if(f[m][s]<n){ puts("-1"); continue; } for(int x=0;x<=m;x++){ if(f[x][s]>=n){ printf("%d ",m-x); break; } } } return 0; }