1、題目來(lái)源：POI98 Problem7者：情況：可以通過(guò)貪心法解決。理由：此題的數(shù)據(jù)規(guī)模不小，而且關(guān)系到 2 的指數(shù)級(jí)，不太可能用搜索，因此我考慮到用貪心算法來(lái)解決，關(guān)于如何貪心以及貪心算法的正確性我考慮了很長(zhǎng)時(shí)間，我個(gè)人覺(jué)得這是一道值得一做的題目。想與大家探討一下。POI V Stage2 Problem 3How to packcontainers?Products of a factory are packed the same bases. A height of a box iso cylindrical boxes. All boxes havea non-negativeeger

2、 being aerof 2, i.e. it is equal to 2i for some i=0,1,2,.The number i (exponent)is called a size of a box. All boxes conta may be different. Goods produced earhe same goods but their value are cher. The managementrdecided,t the oldest (chest) goods should be sold out. From are alson athe warehouse g

3、oods are transported in containers. Containerscylindrical. A diameter of each container is a littiggerdiameter of a box, sot boxes can be easily puto containers. A heightof a container is a non-negativeer of 2. This number is called a sizeof a container. For safe transport containers should be tight

4、ly packed with boxes, i.e. the sum of heights of boxes placed in a container have to be equal to the height of this container. A set of containers was delivered to the warehouse. Check if it issible to pack all thecontainers tight with boxest are currently storedhe warehouse.If so, find the minimal

5、value of goods these containers.t can be tightly packedoExleConsider a warehouse with 5 boxes. Their sizes and values of their contents are given below:1132132514Two containers of size 1 and 2 can be tightly packed with two boxes of total value 3, 4 or 5, or three boxes with total value 9. The conta

6、iner of size 5 cannot be tightly packed with boxes fromthe warehouse.TaskWrite a programt:reads descriptions of boxes (size, value) from a warehouse and descriptions of containers(how many containers of a given size we have) from the text file PAK.IN;checks if all containers can be tightly packed wi

7、th boxes from the warehouse and if so,computes the minimal value of goodst can be tightly packedo these containers;writes the result to the text file PAK.OUT.Inputheline of the input file PAK.here is aneger n, 1=n=10000, which is the numberof boxes in the warehouse. In each of the following n lines

8、there are written two non-negativeegers separated by a single space. These numbers describe a singox.of them is the sizeof the box and the second - the value of goods containedhis box. The size is not greatern1000 and the value is not greatern 10000. The next line contains aitiveeger q, which isthe

9、number of different sizes of containers delivered to the warehouse. In each of the following qlines there are twoitiveegers separated by a single space. Theeger is the size of aal number ofcontainer and the second one is the number of containers of this size. Thecontainers is 5000, a size of a conta

10、iner is not greatern 1000.OutputYour program should write to theand only line of the file PAK.OUTa single word NIE (whieans NO in Polish) if it is notsible to pack the containersfrom the given set tight with the boxes from the warehouse, ora singleeger equal to the minimal value of goods in boxes wi

11、th which all thecontainers from the given set can be packed tight.S5le Input1 12 1Sle Output3POI98Problem7怎樣裝容器？一個(gè)公司生產(chǎn)的產(chǎn)品被裝進(jìn)圓柱型的盒子。所有的盒子有著同樣的底部。盒子的高度是 2的冪次，等于 2i (i=0,1,2,)，指數(shù) i 被稱(chēng)為盒子的大小。所有的盒子都裝著同樣的貨物，但是它們的價(jià)值可能不同。早期生產(chǎn)的貨物要便宜些。管理者決定，將最早生產(chǎn)的貨物(最便宜)最先出售。在倉(cāng)庫(kù)中貨物被送進(jìn)容器中。容器同樣也是圓柱型。每個(gè)容器的直徑要比盒子稍大一些，所以盒子可以容易地放進(jìn)容

12、器中。容器的高度也是 2 的冪次。指數(shù)被稱(chēng)為容器的大小。為了安全地運(yùn)送容器，容器必須緊緊地裝滿(mǎn)盒子，就是說(shuō)被裝入容器的盒子的高度總和應(yīng)等于容器的高度。一些容器已經(jīng)被送到了倉(cāng)庫(kù)。檢查是否可能將容器用盒子裝滿(mǎn)，如果可能的話，求出被裝進(jìn)容器的貨物的價(jià)值和的最小值。例子倉(cāng)庫(kù)中有 5 個(gè)盒子。它們的大小及價(jià)值給出如下：兩個(gè)容器大小分別為 和 2 可以被兩個(gè)盒子填滿(mǎn)可能得到的價(jià)值總和為 3，4 或 5，或者被三個(gè)盒子填滿(mǎn)而得到總價(jià)值 9。大小為 5 的容器不可能被這些盒子填滿(mǎn)。任務(wù)寫(xiě)一個(gè)程序：從文件 PAK.IN 中倉(cāng)庫(kù)中盒子的描述(大小，價(jià)值)，和容器的描述(大小，數(shù)量)檢查所有的容器是否能被倉(cāng)庫(kù)中的盒子裝滿(mǎn)，如果可以，則計(jì)算出所有貨物價(jià)值總和的最小值。將結(jié)果輸出到文件 PAK.OUT輸入輸入文件 PAK.IN 的第一行有一個(gè)整數(shù) n，1=n=10000，表示倉(cāng)庫(kù)中盒子的個(gè)數(shù)。在接下來(lái)的 n 行中，每行有兩個(gè)非負(fù)整數(shù)，中間有一個(gè)空格。兩個(gè)數(shù)字描述了一個(gè)盒子。第一個(gè)數(shù)字表示盒子的大小，第二個(gè)數(shù)字表示盒子中貨物的價(jià)值。盒子的大小不會(huì)超過(guò) 1000，并且價(jià)值不會(huì)超過(guò) 10000。接下來(lái)的一行有一個(gè)正整數(shù) q，表示不同大小的容器的種類(lèi)數(shù)目。在接下來(lái)的 q 行中，每行