• <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:    多重背包問題。選定總價值的一半作為背包容量V,選定物件開始加入。            
             4 How to Do:    如描述。
             5   */
             6 #include <stdio.h>
             7 #include <string.h>
             8 int value[51],num[51];
             9 int dp[250002];
            10 int main(){
            11     int i,j,t,sum,half;
            12     while (scanf("%d",&t)&&t>=0){
            13         memset(dp,0,sizeof(dp));    dp[0]=1;
            14         sum=0;
            15         for(i=0;i<t;i++){
            16             scanf("%d%d",&value[i],&num[i]);
            17             sum+=value[i]*num[i];
            18         }
            19         half=sum/2;//取總價值一半為背包的容量
            20         for(i=0;i<t;i++){
            21             while(num[i]--){//用常規的多重背包做,必超時
            22                 for(j=half-value[i];j>=0;j--){
            23                     if(dp[j])    dp[j+value[i]]=1;
            24                 }
            25             }    
            26         }
            27         while(!dp[half]) half--;//尋找最接近一半價值的
            28         printf("%d %d\n",sum-half,half);
            29     }
            30 } 
            31 
            posted on 2012-03-09 20:14 Leo.W 閱讀(308) 評論(0)  編輯 收藏 引用
            久久精品中文字幕久久| 精品乱码久久久久久久| 亚洲国产精品热久久| 国产精品免费久久| 伊人久久大香线蕉综合网站| 囯产极品美女高潮无套久久久 | 久久精品极品盛宴观看| 亚洲欧美一区二区三区久久| 无码人妻久久一区二区三区 | 美女久久久久久| 亚洲国产成人久久一区久久| 天天躁日日躁狠狠久久| 99久久综合国产精品二区| 狠狠色丁香久久婷婷综合蜜芽五月| 久久99国产精品久久99小说| 久久国产精品77777| 久久久无码一区二区三区| 国产精品毛片久久久久久久| 2021国内久久精品| 久久99精品久久久久久水蜜桃| 久久亚洲国产成人精品无码区| 人妻精品久久久久中文字幕一冢本| 中文字幕成人精品久久不卡| 香蕉久久久久久狠狠色| 国内精品久久久久久野外| 免费无码国产欧美久久18| 久久国产美女免费观看精品| 欧美精品一区二区精品久久| 精品国产乱码久久久久久郑州公司 | 国产精品久久国产精品99盘| 久久综合久久美利坚合众国| 久久综合成人网| 久久播电影网| 国产精品美女久久久久av爽| 国产一级持黄大片99久久| 久久夜色精品国产噜噜噜亚洲AV| 久久久久亚洲精品无码网址| 国产精品一久久香蕉产线看| 久久99国产综合精品| 国产产无码乱码精品久久鸭| 99久久免费国产精精品|