Yulin─學.想.做.

題意： 有一些不同的磚塊，每個磚塊有一定的高度、數量、和最大高度限制，輸入第一列會給一個數字n，代表磚塊的種類，接下來n列會給每個磚塊的資訊，每列3個數字，(高度, 最大高度限制, 數量)，所謂最大高度限制是指，假設現在只有一種磚塊，資訊是2, 5, 100，2 + 2 + 2 > 5，雖然磚塊數量很多，但因為這種磚塊不能超過高度5，所以根據這些磚塊，我堆磚塊高度最高就只能到4，題目要求給定磚塊資訊下、各種磚塊滿足最大高度限制下，堆這些磚塊所能達到的最高高度是多少 解題思路： 多重背包問題(物品是有限的)，把高度想成背包重量上限，磚塊就是物品，現在物品的重量和價值的值一樣，比較不一樣的一點是，這個題目並沒給出一個有明確重量上限的背包要你去塞東西，而是求在滿足各種磚塊的最大高度限制下，所能堆出的磚塊堆最大高度是多少 很明顯的一點，堆出的最大高度 <= 所有磚塊裡的最大高度限制，因為不能超過磚塊的最大高度限制，所以我就想對於1 ~ n種磚塊，假設第i種磚塊的最大高度限制是max[i]、高度是h[i]，對於第i種磚塊，從背包重量上限max[i] ~ h[i]去考慮放或不放，整個流程做完，再從記錄狀態的DP陣列的末端開始往回找，找第一個DP[index] = index的就是了 可是結果TLE，後來改用以2為基底的數量湊堆的方式下去考慮，結果是錯的，這有點微妙，解釋起來有點麻煩，簡而言之，如果上述流程不是從最大高度限制最低的開始，依序增加的去考慮的話會錯... Code：

題意： 某銀行想提供一個提鈔機以供提錢，input有數列、以EOF結尾，每列第一個數字表示現在想提的金額數目，第二個數字表示提款機目前有多少幣值的錢，以它給的第一個範例輸入來說 735 3 4 125 6 5 3 350 第二個數字是3，代表提款機目前有3個幣值的錢，後面的3對資料，每對都是(數量, 幣值)，因此$125的有4張、$5的有6張、$350的有3張，而3*125 + 350 + 2*5 = 735，代表這台提款機可以供應想要的確切金額數目735，如果可以供應想要的確切金額，就印出金額數字，如果無法exactly供應，就印0 解題思路： 典型多重背包，稍微轉換一下就清楚了，把一個錢轉成一個物品(價值和重量相等的物品)、把要換出的金額數目想成背包的重量上限，現在等同是問給一個有限重量的背包，還有各個價值和重量的值相等的物品，有辦法塞東西剛好塞到背包的重量上限嗎？ 設背包重量上限是MAX，某錢j的幣值是money[j]、j從1到n，某錢j的數量是num[j]，那就是從錢第1項到第n項，分別跑一次0/1背包的演算法，考慮某錢j的第k個要放還是不放，整個流程跑完，如果記錄狀態的DP陣列第MAX項的值=MAX，代表可以剛好塞到背包的重量上限，也就是提款機可以供應想要的確切數目 喔對了，這題目我原本用上述這樣直接的方法去解，結果TLE，後來回去讀助教投影片，有更快的方法，就是不要一個一個考慮，可以把好幾個東西壓縮成一個來考慮， 數目是以2為基底 ，例如13可以把它拆成1 + 2 + 4 + 6，因為1 ~ 13之間的任何一個數字，一定可以由1, 2, 4, 1~6(之中一個)，挑幾個來組成，所以一樣可以考慮到所有情況，只是計算的次數就減少了、減少運算時間，這樣才在限制時間內完成 Code：