PAT 1020月餅月餅は中国人が中秋節に食べる伝統的な食品で、地域によっていろいろな風味の月餅があります.すべての種類の月餅の在庫量、総価格、市場の最大需要量を指定します.最大収益はどのくらいの販売時に一部を取り出すことができますか.
1020月餅(25分)
月餅は中国人が中秋節に食べる伝統的な食品で、地域によっていろいろな風味の月餅があります.すべての種類の月餅の在庫量、総価格、市場の最大需要量を与えて、得ることができる最大収益はいくらですか.
注意:販売時に在庫の一部を取り出すことができます.3種類の月餅があれば、その在庫量はそれぞれ18、15、10万トンで、総価格はそれぞれ75、72、45億元です.市場の最大需要量が20万トンしかない場合、私たちの最大収益戦略は15万トンの2種類目の月餅と5万トンの3種類目の月餅を全部売って、72+45/2=94.5(億元)を得るべきだ.(タイトルソースPAT、侵入削除)
入力フォーマット:入力ごとにテスト例が含まれます.各試験例は、1000を超えない正の整数Nが月餅の種類数を表し、500(万トン単位)を超えない正の整数Dが市場の最大需要量を表す.その後、一行はN個の正数を与えて月餅ごとの在庫量(万トン単位)を表す.最後の行はN個の正数を与えて各月餅の総価格(億元単位)を表す.数字の間はスペースで区切られています.
出力フォーマット:各テスト例に対して、1行に最大収益を出力し、億元単位で小数点以下2桁まで正確にします.
入力例:3 20 18 15 10 75 72 45
出力サンプル:94.50
-私の考えと解決策-
構想
タイトルの最大収益は、先に単価の大きい月餅を売ることです.
リュックサック法を運用することができます(分からない場合は無視できます)
コード#コード#
月餅は中国人が中秋節に食べる伝統的な食品で、地域によっていろいろな風味の月餅があります.すべての種類の月餅の在庫量、総価格、市場の最大需要量を与えて、得ることができる最大収益はいくらですか.
注意:販売時に在庫の一部を取り出すことができます.3種類の月餅があれば、その在庫量はそれぞれ18、15、10万トンで、総価格はそれぞれ75、72、45億元です.市場の最大需要量が20万トンしかない場合、私たちの最大収益戦略は15万トンの2種類目の月餅と5万トンの3種類目の月餅を全部売って、72+45/2=94.5(億元)を得るべきだ.(タイトルソースPAT、侵入削除)
入力フォーマット:入力ごとにテスト例が含まれます.各試験例は、1000を超えない正の整数Nが月餅の種類数を表し、500(万トン単位)を超えない正の整数Dが市場の最大需要量を表す.その後、一行はN個の正数を与えて月餅ごとの在庫量(万トン単位)を表す.最後の行はN個の正数を与えて各月餅の総価格(億元単位)を表す.数字の間はスペースで区切られています.
出力フォーマット:各テスト例に対して、1行に最大収益を出力し、億元単位で小数点以下2桁まで正確にします.
入力例:3 20 18 15 10 75 72 45
出力サンプル:94.50
-私の考えと解決策-
構想
タイトルの最大収益は、先に単価の大きい月餅を売ることです.
リュックサック法を運用することができます(分からない場合は無視できます)
コード#コード#
#include
using namespace std;
#include
typedef struct backbag{
float weight; //
float price; //
float value; //
}backbag;
bool cmp(backbag a,backbag b)
{
return a.value>b.value; //
}
int main()
{
int i;
int n;
float money=0;
float sum;
scanf("%d%f",&n,&sum);
backbag s[n];
for(i=0;i<n;i++)
{
scanf("%f",&(s[i].weight));
}
for(i=0;i<n;i++)
{
scanf("%f",&(s[i].price));
s[i].value=s[i].price/s[i].weight;
}
sort(s,s+n,cmp);
for(i=0;i<n;i++)
{
if(sum<s[i].weight)
break;
money+=s[i].price;
sum-=s[i].weight;
}
money+=sum*s[i].value;
printf("%.2f
",money);
return 0;
}