首页 > 代码库 > hdu1864_简单01背包

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]); float ans = 0.0f; for(int i=0;i<=bound;i++) ans=MAX(ans,dp[i]); printf("%.2f\n",ans/100); } return 0; }

 

hdu1864_简单01背包