1.物品可切分的背包问题，贪心算法可解。
2.卡在测试点2比较久，结果发现amount也需要使用double才能通过，使用long long或者int都不行。
3.贪心算法，每次取单位价格最高的mooncake。
存储结构
struct mooncakeNode{
double amount;//需要使用double，才能通过测试点2
double price;
double unitPrice;
mooncakeNode() :amount(0), price(0), unitPrice(0){};
};
Mooncake is a Chinese bakery product traditionally eaten during the Mid-Autumn Festival. Many types of fillings and crusts can be found in traditional mooncakes according to the region’s culture. Now given the inventory amounts and the prices of all kinds of the mooncakes, together with the maximum total demand of the market, you are supposed to tell the maximum profit that can be made.
Note: partial inventory storage can be taken. The sample shows the following situation: given three kinds of mooncakes with inventory amounts being 180, 150, and 100 thousand tons, and the prices being 7.5, 7.2, and 4.5 billion yuans. If the market demand can be at most 200 thousand tons, the best we can do is to sell 150 thousand tons of the second kind of mooncake, and 50 thousand tons of the third kind. Hence the total profit is 7.2 + 4.5/2 = 9.45 (billion yuans).
Input Specification:
Each input file contains one test case. For each case, the first line contains 2 positive integers N (<=1000), the number of different kinds of mooncakes, and D (<=500 thousand tons), the maximum total demand of the market. Then the second line gives the positive inventory amounts (in thousand tons), and the third line gives the positive prices (in billion yuans) of N kinds of mooncakes. All the numbers in a line are separated by a space.
Output Specification:
For each test case, print the maximum profit (in billion yuans) in one line, accurate up to 2 decimal places.
Sample Input:
3 200 180 150 100 7.5 7.2 4.5
Sample Output:
9.45
AC代码：
//#include<string>
//#include<stack>
//#include<unordered_set>
//#include <sstream>
//#include "func.h"
//#include <list>
#include <iomanip>
#include<unordered_map>
#include<set>
#include<queue>
#include<map>
#include<vector>
#include <algorithm>
#include<stdio.h>
#include<iostream>
#include<string>
#include<memory.h>
#include<limits.h>
#include<stack>
using namespace std;
/*
3 2000
180 150 100
7.5 7.2 4.5
3 20
180 150 100
7.5 7.2 4.5
0 20
3 0
180 150 100
7.5 7.2 4.5
3 1
180 150 100
7.5 7.2 4.5
*/
struct mooncakeNode{
double amount;//需要使用double，才能通过测试点2
double price;
double unitPrice;
mooncakeNode() :amount(0), price(0), unitPrice(0){};
};
bool cmp(const mooncakeNode&a, const mooncakeNode&b)
{
if (a.amount == b.amount && a.price >= b.price) return true;
else
return (double)a.price*b.amount > (double)b.price*a.amount;
}
int main(void)
{
int n, marketNeed;
cin >> n >> marketNeed;
vector<mooncakeNode> mooncake(n);
for (int i = 0; i < n; i++)
{
cin >> mooncake[i].amount;
}
for (int i = 0; i < n; i++)
{//输入总价格和求出单位价格
cin >> mooncake[i].price;
if (mooncake[i].amount == 0)
{
mooncake[i].price = 0;
mooncake[i].unitPrice = 0;
}
else
mooncake[i].unitPrice = mooncake[i].price / mooncake[i].amount;
}
sort(mooncake.begin(), mooncake.end(), cmp);
double profit=0;
for (int i = 0; i < n && marketNeed!=0; i++)
{
if (mooncake[i].amount == marketNeed)
{//如果刚好相等，则全部要了
profit += mooncake[i].price;
marketNeed -= mooncake[i].amount;
}
else if (mooncake[i].amount < marketNeed)
{//如果数量小于市场需要，则全部要了
profit += mooncake[i].price;
marketNeed -= mooncake[i].amount;
}
else
{//如果数量大于市场需要，则取市场需要部分即可
profit += mooncake[i].price*marketNeed/mooncake[i].amount;
marketNeed = 0;
}
}
printf("%.2lf", profit);
//cout << setprecision(2) << profit << endl;
return 0;
}