網頁

2014年5月1日 星期四

POJ 1742 Coins

題意:
    有N種硬幣,每種硬幣價值A[i]元以及該種硬幣的數量為C[i],問這些硬幣在最多總合為M元的限制下有幾種組合數?

想法:
    01背包,dp[i]=true表示i元可以被組合出來,最後看dp[1]~dp[M]有幾個true就是答案。這題時間限制嚴格,因此用POJ 1276那篇的方法還是會TLE,因此在底下code22行,我們知道如果j是從M~0表示一次放一個物品,每種要做C[i]次,現在22行j從0開始~M,是用無限背包的方式,先把物品當作無限個,類似greedy的方式,然後用個num陣列來計數,這樣每種物品都只要跑1次就可以了。