• <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  評(píng)論-6  文章-0  trackbacks-0
             1 /*
             2 Author:    Leo.W
             3 Descriptipn:    一個(gè)多重背包的問題,給定儲(chǔ)物罐的容納量W,和提供的不同種類錢幣的價(jià)值與質(zhì)量來估算罐中錢幣的最小價(jià)值
             4 How to Do:    兩層for循環(huán),DP[j]=max{DP[j-w[i]*k]+v[i]*k}(k<j/w[i]);初始化時(shí)需注意的是DP[0]初值為零,數(shù)組其他均為負(fù)無窮。
             5   */
             6 #include <stdio.h>
             7 #include <iostream>
             8 #include <string.h>
             9 using namespace std;
            10 #define MAXSIZE 10000
            11 #define wupin 500
            12 #define MINS -0x7fffffff-1
            13 int DP[MAXSIZE];
            14 int w[wupin];
            15 int v[wupin];
            16 int main(){
            17     //freopen("in.txt","r",stdin);
            18     int i,j,t;
            19     scanf("%d",&t);
            20     while (t--){
            21         int wa,wb;
            22         scanf("%d%d",&wb,&wa);
            23         int weight=wa-wb;
            24         for(i=0;i<=weight;i++)
            25             DP[i]=MINS;
            26         DP[0]=0;
            27         int moneyKinds;
            28         scanf("%d",&moneyKinds);
            29         for(i=0;i<moneyKinds;i++)
            30             scanf("%d%d",&v[i],&w[i]);
            31         for(i=0;i<moneyKinds;i++){            
            32             for(j=w[i];j<=weight;j++){//此處是關(guān)鍵
            33                 if((DP[j]>DP[j-w[i]]+v[i]&&DP[j-w[i]]+v[i]>0)||DP[j]<0)
            34                     DP[j]=DP[j-w[i]]+v[i];
            35             }
            36         }
            37         if(DP[weight]>0)
            38             printf("The minimum amount of money in the piggy-bank is %d.\n",DP[weight]);
            39         else
            40             printf("This is impossible.\n");
            41 
            42     }
            43     return 0;
            44 } 
            45 
            posted on 2012-03-12 20:16 Leo.W 閱讀(241) 評(píng)論(0)  編輯 收藏 引用

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


            久久久久久狠狠丁香| 精品久久久久成人码免费动漫 | 国产精品免费久久久久久久久| 成人免费网站久久久| 99久久国产综合精品成人影院| 亚洲精品综合久久| 久久91精品久久91综合| 日本加勒比久久精品| 精品综合久久久久久97超人| 亚洲精品无码久久不卡| 久久综合综合久久97色| 久久精品国产亚洲AV久| 国产激情久久久久影院老熟女| 亚洲国产精品18久久久久久| 久久99精品久久久久久噜噜| 色综合久久无码五十路人妻| 久久人人爽人人爽人人片AV麻豆 | 久久久无码人妻精品无码| 中文精品久久久久人妻不卡| 97久久超碰成人精品网站| 久久久亚洲AV波多野结衣| 成人国内精品久久久久影院VR| 色欲久久久天天天综合网| 久久99精品国产麻豆婷婷| 久久精品这里热有精品| 伊人久久综合无码成人网| 久久久久国色AV免费看图片| AV无码久久久久不卡蜜桃| 久久99这里只有精品国产| 久久精品亚洲男人的天堂| 91亚洲国产成人久久精品网址| 久久亚洲sm情趣捆绑调教| 亚洲美日韩Av中文字幕无码久久久妻妇| 26uuu久久五月天| 久久电影网一区| 99久久99久久精品国产| 亚洲国产精品热久久| 99久久精品免费看国产免费| 久久99亚洲综合精品首页| 久久久中文字幕日本| 久久无码一区二区三区少妇 |