• <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)  編輯 收藏 引用
            色婷婷噜噜久久国产精品12p| 久久精品国产半推半就| 亚洲国产精品无码久久青草| 久久精品免费全国观看国产| 国内精品伊人久久久久777| 久久国产精品一国产精品金尊| 久久亚洲综合色一区二区三区| 久久精品成人欧美大片| 久久人人爽人人人人爽AV| 久久免费视频观看| 久久人人爽人人人人爽AV| 亚洲精品高清国产一久久| 久久只有这里有精品4| 99精品国产在热久久无毒不卡| 久久久久九九精品影院| 久久久久亚洲av无码专区喷水 | 热久久国产精品| 久久久噜噜噜久久中文字幕色伊伊 | 熟妇人妻久久中文字幕| 久久久久国产| 99久久人人爽亚洲精品美女| 一本色道久久88精品综合| 亚洲AⅤ优女AV综合久久久| 久久电影网一区| www久久久天天com| 伊人久久综合精品无码AV专区| 久久久久无码中| 亚洲午夜精品久久久久久人妖| 麻豆一区二区99久久久久| 久久亚洲AV无码精品色午夜麻豆| 久久精品国产72国产精福利| 91精品国产高清久久久久久91 | 97超级碰碰碰碰久久久久| www久久久天天com| 77777亚洲午夜久久多喷| 久久久久人妻一区精品色 | 99久久国产综合精品麻豆| 久久精品国产久精国产思思| 久久天堂AV综合合色蜜桃网| 久久国产精品成人片免费| 国产精品一区二区久久精品|