• <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>

            coreBugZJ

            此 blog 已棄。

            0-1背包問題——算法作業 3.2,EOJ 1052

            0-1背包問題

            Time Limit:1000MS Memory Limit:30000KB
            Total Submit:796 Accepted:276

            Description

            已知n個物體{1,2,3....n}與一個背包。物體i的重量為Wi > 0,價值為Pi > 0 (i=1,2,...n),背包容量為M > 0。

            求在不超過背包容量的情況下,使得裝進去的物體的價值最高。

            Input

            第一行為一個正整數N,表示有幾組測試數據。
            每組測試數據的第一行為兩個整數n和M,0<n<=20,0<M<100000.
            再下去的n行每行有兩個整數Wi和Pi, 0<Wi,Pi<10000.

            Output

            對于每組測試數據,輸出一行,只含一個整數,表示裝進去物體的價值最高值。

            Sample Input

            1
            5 10
            2 6
            2 3
            6 5
            5 4
            4 6

            Sample Output

            15

            Source

            ECNU算法作業


            空間優化至 O ( m ) :

             1 #include <stdio.h>
             2 #include <string.h>
             3 
             4 #define  M  100003
             5 
             6 int f[M];
             7 
             8 int main(){
             9         int td, n, m, j, w, p;
            10         scanf( "%d"&td );
            11         while( td-- ){
            12                 scanf( "%d%d"&n, &m );
            13                 memset( f, 0sizeof(f) );
            14                 while( n-- ){
            15                         scanf( "%d%d"&w, &p );
            16                         for( j = m; j >= w; --j ){
            17                                 if( f[ j - w ] + p > f[ j ] ){
            18                                         f[ j ] = f[ j - w ] + p;
            19                                 }
            20                         }
            21                 }
            22                 printf( "%d\n", f[ m ] );
            23         }
            24         return 0;
            25 }
            26 


            posted on 2011-04-18 16:08 coreBugZJ 閱讀(339) 評論(0)  編輯 收藏 引用 所屬分類: 課內作業

            久久精品国产亚洲AV无码麻豆| 亚洲一区二区三区日本久久九| 欧美精品丝袜久久久中文字幕 | 色综合久久无码五十路人妻| 久久婷婷五月综合色奶水99啪 | 国产精品久久久99| 狠狠久久综合伊人不卡| 国内精品久久久久久不卡影院 | 国产精品久久久久久久久免费| 91久久精品国产91性色也| 久久亚洲AV无码精品色午夜| 午夜天堂精品久久久久| 久久精品国产亚洲5555| 成人妇女免费播放久久久| 久久无码人妻精品一区二区三区| 久久久久亚洲AV无码专区首JN | 中文字幕久久波多野结衣av| 99久久中文字幕| 国产精品久久久久久久久软件| 精品九九久久国内精品| 精产国品久久一二三产区区别| 色综合久久天天综合| 久久男人Av资源网站无码软件| 无码任你躁久久久久久| 久久精品嫩草影院| 国产精品禁18久久久夂久| 亚洲午夜久久久久妓女影院| 亚洲精品99久久久久中文字幕| 日韩亚洲欧美久久久www综合网| 久久久精品人妻一区二区三区蜜桃 | 天天爽天天爽天天片a久久网| 人妻少妇久久中文字幕| 99久久夜色精品国产网站| 精品久久久久久无码不卡| 久久久不卡国产精品一区二区| 久久精品国产秦先生| 99久久精品国内| 青青国产成人久久91网| 国产精品成人99久久久久91gav| segui久久国产精品| 老司机国内精品久久久久|