I NEED A OFFEER（欲張り）
リンク:http://acm.hdu.edu.cn/showproblem.php?pid=1203
Problem:
I NEED A OFFEER
Time Limit：2000/1000 MS（Java/Others） Memory Limit：65536/32768 K（Java/Others）Total Submission（s）：16871 Acceepted Submission(s)：6739
Problem Description
Speaklessは早くから海外に行きたいと思っています。今はもう必要な試験を全部終えました。準備すべき資料を全部用意しました。そこで、学校を申請しなければなりません。海外のどの大学を申請するにも、一定の申請費用を支払う必要があります。これは驚くべきことです。Speaklessはお金があまりなくて、全部でn万ドルだけ集めました。彼はmの学校の中からいくつかのものを選びます。学校ごとに異なる申請費用a（万ドル）があり、Speaklessは彼がこの学校からofferを受ける可能性を見積もっています。学校の間でofferを得るかどうかはお互いに影響しません。「I NEED A OFFEER」と彼は大声で叫んだ。このかわいそうな人を助けてください。計算してください。彼は少なくとも一つのofferの最大確率を受け取ることができます。（Speaklessが複数の学校を選んだら、どの学校のofferでもいいです。）
Input
いくつかのグループのデータが入力されています。データの最初の行には正の整数nが二つあります。m（0<=n==10000,0<=m==10000)
後ろのm行には、各行に2つのデータがあります。i番目の学校の申請費用とofferをもらう可能性があります。
入力の最後に0が二つあります。
Output
各グループのデータは一つの出力に対応しています。Speaklessは少なくとも一つのofferの最大確率を得ることができるということです。百分数で表して、小数点以下の1桁まで精確です。
Sample Input
10 3 4.0.14.5.0.3 0
Sample Output
44.0%
ベント
You shuld use printf(%)to print a'.
Author
Speakless
ソurce
Gardon-DYGG Conteest 2
Recommund
JGS hining | We have carefully selected several simiar probles for you: 2602 1171 2159 2955 1114
My コード:
嗳include using namespace std；struct node｛double f;double f p;double p;｝a[10011];ブックcmp(node a，node b){returnrna.p}intman(){int n，m，i;doublans，p p;while(scanf("%d"、&n，&m)===2){i i if(n==0&&&m=0=0)break;fork;for(i=1====="""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""fp;a[i].p=a[i].fp/a[i].f;sort(a+1,a+m+1,cmp);pp=1;for(i=1;i+)｛if(n==a[i].f){n==a=a[i].f;pp==a.pr=f="(%return 0;
もう一つの方法を添付します。（0-1バックパックdp実現）
以下のコードは以下の通りです。http://blog.163.com/wuguojin03@126/blog/static/1754113120911346887/
状態：f[j]：j元を入れたら、offerの最小確率が得られません。
状態移行：f[j]=min｛f[j]，f[j-cost[i]*（1-per[i]）｝
初期値：f[]は1
ソースコード:
嗳include using namespace std；int main（）{int n，m，i，j，costt[1001];doublper[1001]，f[10010001]///f[j]：j元を投じたが、oferの最小確率while（scanf（"%d"、&n，&m）&（n！=0|𞓜m======================================================""""""""""""""""""""""""""""""""""""""""""""""""""""は、小さいf[j]=f[j-cost[i]*（1 per[i]）;printf（“%1.1 lf%”、（1-f[n]＊100）、｝return 0；
Problem:
I NEED A OFFEER
Time Limit：2000/1000 MS（Java/Others） Memory Limit：65536/32768 K（Java/Others）Total Submission（s）：16871 Acceepted Submission(s)：6739
Problem Description
Speaklessは早くから海外に行きたいと思っています。今はもう必要な試験を全部終えました。準備すべき資料を全部用意しました。そこで、学校を申請しなければなりません。海外のどの大学を申請するにも、一定の申請費用を支払う必要があります。これは驚くべきことです。Speaklessはお金があまりなくて、全部でn万ドルだけ集めました。彼はmの学校の中からいくつかのものを選びます。学校ごとに異なる申請費用a（万ドル）があり、Speaklessは彼がこの学校からofferを受ける可能性を見積もっています。学校の間でofferを得るかどうかはお互いに影響しません。「I NEED A OFFEER」と彼は大声で叫んだ。このかわいそうな人を助けてください。計算してください。彼は少なくとも一つのofferの最大確率を受け取ることができます。（Speaklessが複数の学校を選んだら、どの学校のofferでもいいです。）
Input
いくつかのグループのデータが入力されています。データの最初の行には正の整数nが二つあります。m（0<=n==10000,0<=m==10000)
後ろのm行には、各行に2つのデータがあります。i番目の学校の申請費用とofferをもらう可能性があります。
入力の最後に0が二つあります。
Output
各グループのデータは一つの出力に対応しています。Speaklessは少なくとも一つのofferの最大確率を得ることができるということです。百分数で表して、小数点以下の1桁まで精確です。
Sample Input
10 3 4.0.14.5.0.3 0
Sample Output
44.0%
ベント
You shuld use printf(%)to print a'.
Author
Speakless
ソurce
Gardon-DYGG Conteest 2
Recommund
JGS hining | We have carefully selected several simiar probles for you: 2602 1171 2159 2955 1114
My コード:
嗳include using namespace std；struct node｛double f;double f p;double p;｝a[10011];ブックcmp(node a，node b){returnrna.p}intman(){int n，m，i;doublans，p p;while(scanf("%d"、&n，&m)===2){i i if(n==0&&&m=0=0)break;fork;for(i=1====="""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""fp;a[i].p=a[i].fp/a[i].f;sort(a+1,a+m+1,cmp);pp=1;for(i=1;i+)｛if(n==a[i].f){n==a=a[i].f;pp==a.pr=f="(%return 0;
もう一つの方法を添付します。（0-1バックパックdp実現）
以下のコードは以下の通りです。http://blog.163.com/wuguojin03@126/blog/static/1754113120911346887/
状態：f[j]：j元を入れたら、offerの最小確率が得られません。
状態移行：f[j]=min｛f[j]，f[j-cost[i]*（1-per[i]）｝
初期値：f[]は1
ソースコード:
嗳include using namespace std；int main（）{int n，m，i，j，costt[1001];doublper[1001]，f[10010001]///f[j]：j元を投じたが、oferの最小確率while（scanf（"%d"、&n，&m）&（n！=0|𞓜m======================================================""""""""""""""""""""""""""""""""""""""""""""""""""""は、小さいf[j]=f[j-cost[i]*（1 per[i]）;printf（“%1.1 lf%”、（1-f[n]＊100）、｝return 0；