• <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:    在限定購買量M,觀看時間L的情況下,在提供的N件電影中挑選出價值最大的。
             4 How to Do:    二維費用背包問題。dp[j][k]=max{dp[j][k],dp[j-c[i]][k-1]+w[i]};
             5   */
             6 #include <iostream>
             7 #include <string.h>
             8 #include <algorithm>
             9 using namespace std;
            10 //#define max(a,b) (a)>(b)?(a):(b)
            11 int c[101],w[101];
            12 int dp[101][1001];
            13 int main(){
            14     //freopen("in.txt","r",stdin);
            15     int t;
            16     scanf("%d",&t);
            17     while (t--){
            18         int n,m,l;
            19         scanf("%d%d%d",&n,&m,&l);
            20         int i,j,k;
            21         for (i=0;i<n;i++)    scanf("%d%d",&c[i],&w[i]);
            22         memset(dp,-1,sizeof(dp));//因為有一維要裝滿,即初始化時不能為零
            23         dp[0][0]=0;
            24         for (i=0;i<n;i++){
            25             for (k=m;k>0;k--){
            26                 for (j=l;j>=c[i];j--){//需要判斷是不是從零累積的到
            27                     if(dp[k-1][j-c[i]]!=-1&&dp[k][j]<dp[k-1][j-c[i]]+w[i])
            28                         dp[k][j]=dp[k-1][j-c[i]]+w[i];
            29                 }
            30             }
            31         }
            32         int ms=0;//此處初始很重要 考慮特殊情況為零值
            33         for(i=l;i>=0;i--)
            34             if(dp[m][i]>ms)
            35                 ms=dp[m][i];
            36         printf("%d\n",ms);
            37     }
            38     return 0;
            39 }
            40 
            posted on 2012-03-14 12:49 Leo.W 閱讀(248) 評論(0)  編輯 收藏 引用

            只有注冊用戶登錄后才能發(fā)表評論。
            網(wǎng)站導(dǎo)航: 博客園   IT新聞   BlogJava   博問   Chat2DB   管理


            亚洲一本综合久久| 久久久久香蕉视频| 午夜精品久久久久久毛片| 亚洲国产精品无码久久久蜜芽 | 91亚洲国产成人久久精品| 久久中文字幕视频、最近更新| 久久久久久久精品成人热色戒| 国产精品一久久香蕉国产线看观看| 狠狠精品干练久久久无码中文字幕| 亚洲精品无码久久毛片| 91精品国产综合久久婷婷| 中文字幕精品久久久久人妻| 国产精品99久久精品| 欧美久久久久久| 久久精品国产99久久丝袜| 国内精品人妻无码久久久影院| 久久久久女教师免费一区| 国产精品久久久久久一区二区三区 | 18岁日韩内射颜射午夜久久成人| 国产日韩欧美久久| 久久最近最新中文字幕大全| 99蜜桃臀久久久欧美精品网站| 久久免费国产精品| 国产精品美女久久久免费| 国产精品对白刺激久久久| 久久亚洲国产成人影院| 色播久久人人爽人人爽人人片aV | 国产精品久久久久久久久久免费| 亚洲AV无码久久精品成人| 影音先锋女人AV鲁色资源网久久| 亚洲v国产v天堂a无码久久| 香蕉久久一区二区不卡无毒影院| 亚洲乱码中文字幕久久孕妇黑人| 亚洲精品乱码久久久久久中文字幕 | 免费观看成人久久网免费观看| 久久99精品久久久久久久不卡 | 久久这里只精品国产99热| 99久久无色码中文字幕人妻| 综合网日日天干夜夜久久 | 久久久亚洲裙底偷窥综合 | 久久久青草久久久青草|