PKU3260-The Fewest Coins

題目：http://poj.org/problem?id=3260
FJ有N(100)種面額為Vi(120)的硬幣，每種硬幣有Ci(10000)個

他想去商店購買價值T(10000)的物品，如果可行的話、可以給較多的總金額來找錢

問最小的支付硬幣數+找回硬幣數(商店擁有無限個各種硬幣)


程式碼：http://codepad.org/lbHX03T0

首先我們想知道，到底最多可能可以給超出T多少錢呢？這關係到數組的範圍

如果把全部的硬幣都捧出去的話可是有100*120*10000=1.2億元呢

這裡提供一個比較安全的上界：以超出的部分來說，使用的同面額硬幣數至多1個
據此可以超出100*120=12000元
(實際上，這題數據不管是開30000還是10120、甚至10060都是會過的)
事後google發現有比這更嚴謹的上界，是10000+120^2


剩下的事情好辦很多，只要建出商家的硬幣表格(完全背包)、FJ的硬幣表格(多重背包)

枚舉超出值x取出最優的DP[x]+DPF[T+x]就可以