首页 > 代码库 > HDU -1864最大报销额(01背包)
HDU -1864最大报销额(01背包)
这道题属于简单的01背包，但是背包问题还算简单，就是前面的细节处理的时候要注意，题意大致说了三条限制吧
1. 只有a, b, c 三种类型的发票可以报销，其它的一律不报销
2. 物品单项的报销额不超过600
3. 每个发票总额不超过1000
有了这三个，还有一个要小心的就是报销额可以为浮点数，所以这里有个小技巧，就是将它乘100，到最后再除以100， 为什么要乘100呢， 因为最后要求保留两位小数
代码如下：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 using namespace std; 5 6 int dp[3000050];//发票张数30*每张总额1000*放大倍数100 = 3000000 7 int main() 8 { 9 char ch;10 double x, y;11 int sum, a, b, c, money[35], t;12 int n, k;13 while (~scanf("%lf %d", &x, &n) && n)14 {15 sum = (int)(x * 100);//将背包的容量放大为整数(这里就是报销的最大值)16 memset(dp, 0, sizeof(dp));17 memset(money, 0, sizeof(money));18 int len = 0;//可报销的列表长度，也就是最后的n19 for (int i = 0; i < n; i++)20 {21 scanf("%d", &k);22 a = b = c = 0;//分别来保存a类型,b类型,c类型23 bool flag = true;24 while (k--)25 {26 scanf(" %c:%lf", &ch, &y);27 t = (int)(y * 100);28 if (ch == ‘A‘ && a + t <= 60000)29 a += t;30 else if (ch == ‘B‘ && b + t <= 60000)31 b += t;32 else if (ch == ‘C‘ && c + t <= 60000)33 b += t;34 else35 flag = false;36 37 }38 if (a + b + c <= 100000 && a <= 60000 && b <= 60000 && c <= 60000 && flag)39 money[len++] = a + b + c;//如果满足以上三个条件40 }41 for (int i = 0; i < len; i++)//01背包核心代码42 {43 for (int j = sum; j >= money[i]; j--)44 if (dp[j] < dp[j - money[i]] + money[i])45 dp[j] = dp[j - money[i]] + money[i];46 }47 printf("%.2f\n", (dp[sum]/100.0));48 }49 return 0;50 }
HDU -1864最大报销额(01背包)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。