• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            隨筆-65  評論-6  文章-0  trackbacks-0
             1 /*
             2 Author:    Leo.W
             3 Descriptipn:典型的01背包問題,對輸入的每組數據【花費及可能性】進行背包判斷,
             4             得到在花費總和是經濟能力范圍內的累計獲offer幾率最大的組合。
             5 How to Do:f[V]=max{f[V],f[V-c[i]]+w[i]}; 
             6         【前后f[V]分別表示前i個大學申請在總花費為V時的最大幾率和前i-1個大學申請在總花費為V時的最大幾率;
             7             f[V-c[i]]表示前i-1個大學在總花費為V-c[i]時的最大幾率,
             8             c[i]表示第i個大學申請的花費,w[i]則表示第i個大學申請成功的幾率】
             9   */
            10 #include <iostream>
            11 #include <string.h>
            12 using namespace std;
            13 double f[100010];
            14 int c[1010];
            15 double w[1010];
            16 int main(){
            17     //freopen("in.txt","r",stdin);
            18     int n,m;
            19     int i,j;
            20     while(scanf("%d%d",&n,&m),m||n){
            21         for(i=0;i<m;i++){
            22             scanf("%d%lf",&c[i],&w[i]);
            23         }
            24         memset(f,0.0,sizeof(f));
            25         for(i=0;i<m;i++){
            26             for(j=n;j>=c[i];j--){//比較是鑒于概率論的知識
            27                 f[j]=f[j]>(1-(1-f[j-c[i]])*(1-w[i]))?f[j]:(1-(1-f[j-c[i]])*(1-w[i]));
            28             }
            29         }
            30         double sum=f[n]*100;
            31         printf("%.1lf%%\n",sum);
            32     }
            33     return 0;
            34 }
            35 
            posted on 2012-03-02 23:59 Leo.W 閱讀(263) 評論(0)  編輯 收藏 引用
            久久Av无码精品人妻系列| 97精品伊人久久久大香线蕉| 欧美一区二区三区久久综| 久久精品人人做人人爽电影蜜月 | 久久人与动人物a级毛片| 亚洲国产另类久久久精品| 国产AⅤ精品一区二区三区久久| 久久精品18| 精品久久久久久无码专区不卡| 欧美久久综合性欧美| 久久AV高清无码| 青青草原综合久久大伊人导航| 少妇高潮惨叫久久久久久| 观看 国产综合久久久久鬼色 欧美 亚洲 一区二区 | 久久精品国产黑森林| 无码国内精品久久人妻| 精品国产一区二区三区久久蜜臀| 区久久AAA片69亚洲| 久久亚洲av无码精品浪潮| 久久成人18免费网站| 少妇精品久久久一区二区三区| 久久久噜噜噜久久中文字幕色伊伊| 久久久精品人妻一区二区三区四 | 伊人久久大香线蕉精品不卡| 久久久免费观成人影院| 97久久久精品综合88久久| 99精品国产99久久久久久97| 九九热久久免费视频| 欧美久久综合性欧美| 77777亚洲午夜久久多喷| 久久精品www人人爽人人| 浪潮AV色综合久久天堂| 伊人久久综合成人网| 国内精品久久久久久久久电影网 | 久久亚洲精品无码观看不卡| 久久综合久久久| 88久久精品无码一区二区毛片| 青青草原综合久久| 久久婷婷国产麻豆91天堂| 国产高清美女一级a毛片久久w| 伊人久久综在合线亚洲2019|