POJ 1276 Cash Machine
題意：
某銀行想提供一個提鈔機以供提錢，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：
留言
張貼留言