#title P08: 泛化物品* 定義考慮這樣一種物品，它并沒有固定的費(fèi)用和價(jià)值，而是它的價(jià)值隨著你分配給它的費(fèi)用而變化。這就是泛化物品的概念。更嚴(yán)格的定義之。在背包容量為V的背包問題中，泛化物品是一個(gè)定義域?yàn)?..V中的整數(shù)的函數(shù)h，當(dāng)分配給它的費(fèi)用為v時(shí)，能得到的價(jià)值就是h(v)。這個(gè)定義有一點(diǎn)點(diǎn)抽象，另一種理解是一個(gè)泛化物品就是一個(gè)數(shù)組h[0..V]，給它費(fèi)用v，可得到價(jià)值h[V]。一個(gè)費(fèi)用為c價(jià)值為w的物品，如果它是01背包中的物品，那么把它看成泛化物品，它就是除了h(c)=w其它函數(shù)值都為0的一個(gè)函數(shù)。如果它是完全背包中的物品，那么它可以看成這樣一個(gè)函數(shù)，僅當(dāng)v被c整除時(shí)有h(v)=v/c*w，其它函數(shù)值均為0。如果它是多重背包中重復(fù)次數(shù)最多為n的物品，那么它對(duì)應(yīng)的泛化物品的函數(shù)有h(v)=v/c*w僅當(dāng)v被c整除且v/c<=n，其它情況函數(shù)值均為0。一個(gè)物品組可以看作一個(gè)泛化物品h。對(duì)于一個(gè)0..V中的v，若物品組中不存在費(fèi)用為v的的物品，則h(v)=0，否則h(v)為所有費(fèi)用為v的物品的最大價(jià)值。[[P07]]中每個(gè)主件及其附件集合等價(jià)于一個(gè)物品組，自然也可看作一個(gè)泛化物品。* 泛化物品的和如果面對(duì)兩個(gè)泛化物品h和l，要用給定的費(fèi)用從這兩個(gè)泛化物品中得到最大的價(jià)值，怎么求呢？事實(shí)上，對(duì)于一個(gè)給定的費(fèi)用v，只需枚舉將這個(gè)費(fèi)用如何分配給兩個(gè)泛化物品就可以了。同樣的，對(duì)于0..V的每一個(gè)整數(shù)v，可以求得費(fèi)用v分配到h和l中的最大價(jià)值f(v)。也即    <code>f(v)=max{h(k)+l(v-k)|0<=k<=v}</code>可以看到，f也是一個(gè)由泛化物品h和l決定的定義域?yàn)?..V的函數(shù)，也就是說，f是一個(gè)由泛化物品h和l決定的泛化物品。由此可以定義泛化物品的和：h、l都是泛化物品，若泛化物品f滿足以上關(guān)系式，則稱f是h與l的和。這個(gè)運(yùn)算的時(shí)間復(fù)雜度取決于背包的容量，是O(V^2)。泛化物品的定義表明：在一個(gè)背包問題中，若將兩個(gè)泛化物品代以它們的和，不影響問題的答案。事實(shí)上，對(duì)于其中的物品都是泛化物品的背包問題，求它的答案的過程也就是求所有這些泛化物品之和的過程。設(shè)此和為s，則答案就是s[0..V]中的最大值。* 背包問題的泛化物品一個(gè)背包問題中，可能會(huì)給出很多條件，包括每種物品的費(fèi)用、價(jià)值等屬性，物品之間的分組、依賴等關(guān)系等。但肯定能將問題對(duì)應(yīng)于某個(gè)泛化物品。也就是說，給定了所有條件以后，就可以對(duì)每個(gè)非負(fù)整數(shù)v求得：若背包容量為v，將物品裝入背包可得到的最大價(jià)值是多少，這可以認(rèn)為是定義在非負(fù)整數(shù)集上的一件泛化物品。這個(gè)泛化物品——或者說問題所對(duì)應(yīng)的一個(gè)定義域?yàn)榉秦?fù)整數(shù)的函數(shù)——包含了關(guān)于問題本身的高度濃縮的信息。一般而言，求得這個(gè)泛化物品的一個(gè)子域（例如0..V）的值之后，就可以根據(jù)這個(gè)函數(shù)的取值得到背包問題的最終答案。綜上所述，一般而言，求解背包問題，即求解這個(gè)問題所對(duì)應(yīng)的一個(gè)函數(shù)，即該問題的泛化物品。而求解某個(gè)泛化物品的一種方法就是將它表示為若干泛化物品的和然后求之。* 小結(jié)本講可以說都是我自己的原創(chuàng)思想。具體來(lái)說，是我在學(xué)習(xí)函數(shù)式編程的 Scheme 語(yǔ)言時(shí)，用函數(shù)編程的眼光審視各類背包問題得出的理論。這一講真的很抽象，也許在“模型的抽象程度”這一方面已經(jīng)超出了NOIP的要求，所以暫且看不懂也沒關(guān)系。相信隨著你的OI之路逐漸延伸，有一天你會(huì)理解的。我想說：“思考”是一個(gè)OIer最重要的品質(zhì)。簡(jiǎn)單的問題，深入思考以后，也能發(fā)現(xiàn)更多。[[Index][首頁(yè)]]--------Copyright (c)  2007  Tianyi CuiPermission is granted to copy, distribute and/or modify this document under the terms of the [[http://www.gnu.org/licenses/fdl.txt][GNU Free Documentation License]], Version 1.2 or any later version published by the Free Software Foundation.