本文共 1724 字，大约阅读时间需要 5 分钟。
#include#include #include #include using namespace std;const int q_max = 1000 * 30 * 100 + 5;const int n_max = 30 + 5;double dp[q_max];double abc[3];double price[n_max];int price_temp[n_max];double q;int q_temp;int n, m;char letter;double value, sum;int flag, pos;void DP(){ memset(dp, 0, sizeof(dp)); for(int i = 0; i < pos; i ++) price_temp[i] = price[i] * 100; q_temp = q * 100; for(int i = 0; i < pos; i ++) for(int j = q_temp; j >= price_temp[i]; j --) dp[j] = max(dp[j], dp[j - price_temp[i]] + price_temp[i]);}int main(){ while(~scanf("%lf %d", & q, & n)) { if(!n) break; memset(price, 0, sizeof(price)); pos = 0; for(int i = 0; i < n; i ++) { scanf("%d", & m); flag = 1; memset(abc, 0, sizeof(abc)); sum = 0; while(m --) { scanf(" %c:%lf", & letter, & value); sum += value; if(letter != 'A' && letter != 'B' && letter != 'C') { flag = 0; continue; } abc[letter - 'A'] += value; if(sum > 1000 || abc[letter - 'A'] > 600) flag = 0; } if(flag) { price[pos] = sum; pos ++; } } DP(); printf("%.2f\n", dp[q_temp] * 1.0 / 100); } return 0;}
题意：
（摘自 键盘上的舞者）
先给出最大的报销额和发票的张数，然后下面是n张发票，每张发票先给出发票上物品的个数，然后给出每种物品和物品的价格注意：
1.只有a，b，c三种物品可以报销，含有其他物品的发票作废2.单样物品的价值不能超过600
3.每张发票总价值不能超过1000
输出最大价值
题解：
将所有的小数化为整数，这样就成了最基础的0-1背包问题。但是判断的时候要小心…就因为中间判断郁闷到现在。
转载地址：http://qctpi.baihongyu.com/