首页 > 代码库 > 01背包水题篇之HDU1864——最大报销额

01背包水题篇之HDU1864——最大报销额

这个题目好果的01,只要把每个数乘以100,就能解决下标的问题了


继续贴代码环节(自己的代码好丑啊~~~)



<span style="font-size:18px;">#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#define maxn 3100000
using namespace std;
int dp[maxn];
int p[31];
int main()
{
    double Q;
    int n,V;
    while(~scanf("%lf%d",&Q,&n)&&n){
        int k=0;
        V=Q*100;
        while(n--){
            int m,flag=1;
            double ts=0,a;
            char s[10];
            cin>>m;
            double va,vb,vc;
            va=vb=vc=0;
            while(m--){
                cin>>s;

                if(s[0]!='A'&&s[0]!='B'&&s[0]!='C'){
                    flag=0;
                }
                else{
                    sscanf(s,"%*[A-Z]:%lf",&a);//我用了下sscanf函数,可以这样输入scanf("%c:%lf",&ch,&a);
                    if(s[0]=='A'){
                        va+=a;
                        if(va>600) flag=0;
                    }
                    if(s[0]=='B'){
                        vb+=a;
                        if(vb>600) flag=0;
                    }
                    if(s[0]=='C'){
                        vc+=a;
                        if(vc>600) flag=0;
                    }
                }
            }
            if(va+vb+vc>1000) flag=0;
            if(flag) p[k++]=(va+vb+vc)*100;
        } 
        memset(dp,0,sizeof dp);
        for(int i=0;i<k;i++){
            for(int j=V;j>=p[i];j--){
                dp[j]=max(dp[j],dp[j-p[i]]+p[i]);//照搬01的方程
            }
        }
        printf("%.2lf\n",1.0*dp[V]/100);//输出转化为double型
    }
    return 0;
}</span>