hdu 1864 最大报销额（01背包）

港控/mmm° 2022-09-18 12:44 130阅读 0赞

http://acm.hdu.edu.cn/showproblem.php?pid=1864

注意题中的条件，不符合条件的直接不考虑

并且，物品的重量价值不是整型，！！！！！！！！！！要整型转换

/***************************
      01 背包
      1.放每个bone到背包 
    
    # 2013-11-20 13:39:35  
    # Time: MS   Memory: K
    # Author: zyh
    ***************************/ 
    
    #include<iostream>
    #include<algorithm>
    #include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
    #include<math.h>
    using namespace std;
    
    int f[3000010];
    double p[35];
    int zeroonepack(int n,int v)
    {
        memset(f,0,sizeof(f));
        for(int i=0;i<n;i++){
            int t = (int)(p[i]*100);  //转换成整数 
            for(int j=v;j>=t;j--){
                if(f[j]<f[j-t]+t)
                    f[j] = f[j-t]+t;
            }
        }
        return f[v];
    }
    int main()
    {
        int j,i,m,n,flag;
        double sum,v,q,a,b,c;
        char ch;
        while(~scanf("%lf %d",&q,&n),n){
            for(j=i=0;i<n;i++) {
                scanf("%d",&m);    
                getchar();
                a=b=c=0; flag = 1;
                while(m--){
                    scanf("%c:%lf",&ch,&v);
                    if(ch!='A' && ch!='B' && ch != 'C') flag = 0;
                    else if(ch=='A') a+=v;
                    else if(ch=='B') b+=v;
                    else if(ch=='C') c+=v;
                    getchar();
                }
                if(a+b+c<=1000 && a<=600 && b<=600 && c<=600 && flag) p[j++] =a+b+c; //题中条件 
            }
            printf("%.2lf\n",1.0*zeroonepack(j,(int)(q*100))/100);
        }
        return 0; 
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，130人围观）

还没有评论，来说两句吧...

相关阅读

相关 HDU 2955 Robberies(01背包）

Robberies Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Othe

墨蓝/ 2022年10月01日 04:54/ 0 赞/ 36 阅读

相关 HDU 1203（01背包）

题意：如题。 include <cstring> include <cstdio> define maxn 1009

- 日理万妓/ 2022年09月20日 11:26/ 0 赞/ 16 阅读

相关 hdu 1864 最大报销额（01背包）

http://acm.hdu.edu.cn/showproblem.php?pid=1864 注意题中的条件，不符合条件的直接不考虑并且，物品的重量价值不是整型

港控/mmm°/ 2022年09月18日 12:44/ 0 赞/ 131 阅读

相关 hdu1203 01背包问题

Speakless很早就想出国，现在他已经考完了所有需要的考试，准备了所有要准备的材料，于是，便需要去申请学校了。要申请国外的任何大学，你都要交纳一定的申请费用，这可是很惊人的

迷南。/ 2022年08月21日 01:25/ 0 赞/ 28 阅读

相关 hdu 1864-最大报销额-贪心

最大报销额 Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others

矫情吗；*/ 2022年08月21日 01:13/ 0 赞/ 107 阅读

相关九度OJ-1025：最大报销额

题目1025：最大报销额时间限制：1 秒内存限制：32 兆特殊判题：否提交：4410 解决：1063 题目描述：现有一笔经费可以报销一定额度的发

ゞ浴缸里的玫瑰/ 2022年08月17日 15:14/ 0 赞/ 133 阅读

相关 HDU-3339-spfa+01背包

In Action Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java

我不是女神ヾ/ 2022年07月11日 11:22/ 0 赞/ 173 阅读

相关 01背包+完全背包 HDU - 5410 

Today is CRB's birthday. His mom decided to buy many presents for her lovely son. S

喜欢ヅ旅行/ 2022年06月17日 09:27/ 0 赞/ 209 阅读

相关问题 : 最大报销额

题目描述现有一笔经费可以报销一定额度的发票。允许报销的发票类型包括买图书（A类）、文具（B类）、差旅（C类），要求每张发票的总额不得超过1000元，每张发票上，单项物品的

客官°小女子只卖身不卖艺/ 2022年06月10日 06:26/ 0 赞/ 113 阅读

相关 HDU 1864(动态规划-01背包)

问题描述: 现有一笔经费可以报销一定额度的发票。允许报销的发票类型包括买图书（A类）、文具（B类）、差旅（C类），要求每张发票的总额不得超过1000元，每张发票上，单项物品的

╰+攻爆jí腚メ/ 2022年06月07日 12:50/ 0 赞/ 190 阅读