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

            oyjpArt ACM/ICPC算法程序設(shè)計(jì)空間

            // I am new in programming, welcome to my blog
            I am oyjpart(alpc12, 四城)
            posts - 224, comments - 694, trackbacks - 0, articles - 6

            pku3309 Unlucky Luke!

            Posted on 2008-08-02 19:35 oyjpart 閱讀(2873) 評(píng)論(0)  編輯 收藏 引用 所屬分類(lèi): ACM/ICPC或其他比賽

            Unlucky Luke!

            By oyjpArt/alpc12

            題意

            n    有2個(gè)倉(cāng)庫(kù),容量為(0 <= V <= 5000) 浮點(diǎn)數(shù)!

            n    有100個(gè)物品,每個(gè)物品容量為(0 <= v[i] <= 100) 整數(shù) 價(jià)值為 m[i] (無(wú)范圍浮點(diǎn)數(shù)!)

            n    現(xiàn)在把這些物品放到2個(gè)倉(cāng)庫(kù)中,求最大的價(jià)值。

            n    如果有放不進(jìn)去的物品,可以切割出一部分放進(jìn)去,但是一旦切割,沒(méi)放進(jìn)進(jìn)去的一部分必須丟棄。

            貪心?

            n    這道題初看上去,很有讓人貪心的沖動(dòng)。

            n    我和alpc42合計(jì)了一下。

            n    根據(jù)A[i].m/A[i].v 作為優(yōu)先級(jí) 給(A, A+n) 排序。

            n    依次將A[0], A[1]…A[n-1]放入倉(cāng)庫(kù),如果放不進(jìn)去了,則切掉。

            n    現(xiàn)在有兩個(gè)倉(cāng)庫(kù),當(dāng)準(zhǔn)備放一個(gè)物品進(jìn)去的時(shí)候,應(yīng)該放到哪個(gè)倉(cāng)庫(kù)呢?

             

            第一次提交

            n    我們倆想了想,覺(jué)得應(yīng)該是放到空閑地方大的倉(cāng)庫(kù),因?yàn)橐M可能把性?xún)r(jià)比高的物品放進(jìn)去。

            n    4144542008-08-01 13:42:41

            n    WrongAnswer

            n    C++

            n    0.9K

            第二次提交

            n    隨后我想出了一種會(huì)讓程序出bug的情況。

            n    就是當(dāng)兩個(gè)物品性?xún)r(jià)比相當(dāng)?shù)臅r(shí)候,應(yīng)該要讓大容量的在前面。因?yàn)橛锌赡苄∪萘康南确胚M(jìn)去,導(dǎo)致大容量的沒(méi)有地方放了,而需要切割。但實(shí)際上可以把小容量的放到小剩余容量的倉(cāng)庫(kù)里面去,而大容量的就可以放到大剩余容量的倉(cāng)庫(kù).

            n    改正提交之后還是Wrong Answer

             

            問(wèn)題在這

            n     思考了一下我發(fā)現(xiàn)其實(shí)上面那個(gè)bug并沒(méi)有解決。假設(shè)A[i].m/A[i].v > A[j].m/A[j].v,按理來(lái)說(shuō)應(yīng)該先放i,再放j。但是加入A[i].v < A[j].v,同樣的有可能先放i再放j會(huì)讓j被迫切割。

            n     那么怎么辦?

            n     隨后我們想到了一種動(dòng)態(tài)規(guī)劃的方法,但是因?yàn)閺?fù)雜度太高,放棄了。這時(shí)候我們發(fā)現(xiàn)手頭有很多題目可以做,就沒(méi)有再做這個(gè)題目了。

            賽后的思考

            n      之所以會(huì)出現(xiàn)這樣的問(wèn)題。在于我們最開(kāi)始的假設(shè):要把性?xún)r(jià)比高的物品放到容量更大的倉(cāng)庫(kù)中。

            n      那么,假如我們枚舉一個(gè)物品放到A倉(cāng)庫(kù)還是B倉(cāng)庫(kù)的話,就可以解決這個(gè)問(wèn)題了。

            n      所謂枚舉,其實(shí)是一個(gè)動(dòng)態(tài)規(guī)劃。

            n      設(shè)dp[i][j] 代表前i個(gè)物品(排序后)都被完全放入了倉(cāng)庫(kù),并且A倉(cāng)庫(kù)已經(jīng)裝了j的容量的物品。顯然我們可以同時(shí)知道B倉(cāng)庫(kù)的容量是多少。

            n      向后推的狀態(tài)方程

            n      dp[i+1][j+A[i+1].v] = Max(dp[i+1][j+A[i+1].v], dp[i][j] + A[i+1].m);

            n      dp[i+1][j] = Max(dp[i+1][j], dp[i][j] + A[i+1].m);

            n      如果一個(gè)倉(cāng)庫(kù)已經(jīng)放不進(jìn)去了,大家可以想想,應(yīng)該是把下一個(gè)物品切割掉放入這個(gè)倉(cāng)庫(kù)中。(如果后面有物品可以放到另外一個(gè)倉(cāng)庫(kù)中,不用擔(dān)心。后面的DP會(huì)覆蓋這種情況)

            n      一個(gè)倉(cāng)庫(kù)放滿了之后,另外一個(gè)倉(cāng)庫(kù)堆放的情況其實(shí)就是貪心了。

            // Solution by alpc12
            #include 
            <stdio.h>
            #include 
            <algorithm>
            using namespace std;

            const int N = 105;
            const double EPS = 1e-7;
            const double INF = 10e100;

            double dp[N][10001], V;
            int n, maxv, vall[N];

            struct Node
            {
                
            int v;

                
            double m;
            };

            bool operator<(const Node&a,const Node&b) {
                
            return a.m/a.v > b.m/b.v;
            }

            Node A[N];

            inline 
            double Max(double a,double b) {
                
            return a > b ? a : b;
            }
            inline 
            double Min(double a,double b) {
                
            return a < b ? a : b;
            }

            double go(double v, int st) {
                
            double ans = 0;
                
            while(v > 0 && st <= n) {
                    
            if(A[st].v <= v) {
                        v 
            -= A[st].v;
                        ans 
            += A[st].m;
                    } 
            else {
                        ans 
            += A[st].m * v/A[st].v;
                        v 
            = 0;
                    }
                    st
            ++;
                }
                
            return ans;
            }

            void solve() {
                
            int i, j, k;
                
            for(i = 0; i <= n; ++i)
                    
            for(j = 0; j <= maxv; ++j)
                        dp[i][j] 
            = -INF;
                dp[
            0][0= 0;
                
                
            double max = 0;
                
            for(i = 0; i <= n; ++i) {
                    
            for(j = 0; j <= vall[i] && j <= V; ++j) if(dp[i][j] != -INF) {
                        max 
            = Max(max, dp[i][j]);
                        
            if(i < n) {
                            
            int k = vall[i] - j;
                            
            if((V-j) >= A[i+1].v) {
                                dp[i
            +1][j+A[i+1].v] = Max(dp[i+1][j+A[i+1].v], dp[i][j] + A[i+1].m);
                            } 
            else {
                                max 
            = Max(max, dp[i][j] + A[i+1].m*(V-j)/A[i+1].v + go(V-k, i+2));
                            }
                            
            if((V-k) >= A[i+1].v) {
                                dp[i
            +1][j] = Max(dp[i+1][j], dp[i][j] + A[i+1].m);
                            } 
            else {
                                max 
            = Max(max, dp[i][j] + A[i+1].m*(V-k)/A[i+1].v + go(V-j, i+2));
                            }
                        }
                    }
                }
                printf(
            "%.4lf\n", max);
            }

            int main()
            {
                //freopen(
            "t.in""r", stdin);

                
            int ntc, i, j;
                scanf(
            "%d"&ntc);
                
            while(ntc--) {
                    scanf(
            "%d %lf"&n, &V);
                    maxv 
            = 0;
                    
            for(i = 1; i <= n; ++i) {
                        scanf(
            "%d"&(A[i].v));
                        maxv 
            += A[i].v;
                    }
                    maxv 
            = Min(maxv, (int)V);
                    
            for(i = 1; i <= n; ++i) {
                        scanf(
            "%lf"&(A[i].m));
                    }
                    sort(A 
            + 1, A + n + 1);
                    vall[
            0= 0;
                    
            for(i = 1; i <= n; ++i) {
                        vall[i] 
            = vall[i-1+ A[i].v;
                    }
                    solve();
                }

                
            return 0;
            }

            亚洲国产精品嫩草影院久久| 久久91这里精品国产2020| 久久亚洲2019中文字幕| 久久综合色区| 亚洲中文久久精品无码| 国产精品久久久亚洲| 久久综合九色综合久99| 久久久久国产精品嫩草影院 | 久久久久亚洲av无码专区| 精品久久无码中文字幕| 久久久久久av无码免费看大片| 久久这里的只有是精品23| 97精品伊人久久大香线蕉app | 久久综合给合久久狠狠狠97色| 99久久精品国产免看国产一区| 伊人久久国产免费观看视频 | 久久性生大片免费观看性| 97久久综合精品久久久综合| 日日狠狠久久偷偷色综合96蜜桃| 中文字幕乱码人妻无码久久 | 无码任你躁久久久久久老妇App| 久久精品国产亚洲AV无码麻豆| 人妻系列无码专区久久五月天| 久久国产精品无码HDAV| 四虎亚洲国产成人久久精品| 国产精品久久精品| 日产精品久久久久久久| 久久精品国产亚洲AV蜜臀色欲 | 久久午夜无码鲁丝片| 久久午夜免费视频| 99久久精品免费观看国产| 91精品国产91久久综合| 亚洲精品无码久久千人斩| 久久国内免费视频| 婷婷久久综合| 亚洲国产成人久久一区WWW| 久久性精品| 国产精品99久久久久久宅男小说| 日本国产精品久久| 久久乐国产综合亚洲精品| 亚洲性久久久影院|