• <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 閱讀(240) 評論(0)  編輯 收藏 引用
            青青热久久国产久精品 | 久久国产福利免费| 久久精品这里热有精品| 久久99久久99精品免视看动漫| 久久福利资源国产精品999| 久久亚洲高清综合| 欧美一区二区久久精品| 久久香综合精品久久伊人| 久久99精品国产麻豆宅宅| 亚洲va中文字幕无码久久不卡 | 久久久久久久久久久免费精品| 国内精品久久久久久久coent| 国产三级观看久久| 久久久久亚洲AV无码去区首| 欧美日韩中文字幕久久久不卡 | 亚洲人成无码www久久久| 精品伊人久久久| 久久精品亚洲日本波多野结衣| 国产精品美女久久久久网| 国产成人无码精品久久久久免费| 久久久久久国产精品美女| 无码任你躁久久久久久老妇App| 亚洲欧美成人综合久久久| 国产V亚洲V天堂无码久久久 | 久久AAAA片一区二区| 久久只有这精品99| 国内精品久久久久影院优| 国产日韩久久免费影院| 99久久精品免费看国产一区二区三区 | 久久综合久久自在自线精品自| 国产精品18久久久久久vr| 久久亚洲av无码精品浪潮| 久久丫精品国产亚洲av不卡| 中文精品久久久久国产网址| 久久无码专区国产精品发布| 中文字幕成人精品久久不卡| 亚洲中文字幕无码一久久区| 久久精品国产亚洲Aⅴ香蕉| 精品久久久久久无码专区| 久久狠狠一本精品综合网| 国产精品美女久久久|