HDU 46DP 之二（01背包问题）

HDU 46DP 之二（01背包问题）

题目：.php?pid=1864
这道题就是都是小数，所以直接扩大100倍。当成正常的背包问题。

#include<bits/stdc++.h>
#define INF 1e18
#define inf 1e9
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define IOS ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std ;
typedef long long ll;
typedef unsigned long long ull;
const int maxn=3000000+10;  
int dp[maxn],v[100];  
int main()  
{  int n,m,cnt;  double a[3],q;  while(cin>>q>>n&&n)  {  cnt=0;  while(n--)  {  memset(a,0,sizeof(a));  char str[10];  cin>>m;  double sum=0;bool flag=1;  while(m--)  {  cin>>str;  sum+=a[str[0]-'A']+=atof(str+2);  if(a[str[0]-'A']>600||sum>1000)  flag=0;  }  if(flag)    v[cnt++]=int(100.0*sum);  }  int dpmax=int(100*q);  for(int i=0;i<=dpmax;i++)   dp[i]=0;  for(int i=0;i<cnt;i++)  for(int j=dpmax;j>=v[i];j--)  dp[j]=max(dp[j-v[i]]+v[i],dp[j]);  cout<<fixed<<showpoint;  cout<<setprecision(2)<<dp[dpmax]/100.0<<endl;  }  
}