網頁

2014年4月29日 星期二

UVa 10465 Homer Simpson

題意:
    有兩種漢堡A和B,吃一個A需要m分鐘,吃一個B需要n分鐘。現在給你t分鐘,問在"剛好用完"t分鐘的情況下最多能吃幾個漢堡k,輸出k;如果沒辦法剛好用完t分鐘,則找最接近t分鐘的k値,輸出k和差幾分鐘。

想法:
    背包問題,重量和物品價值都是時間,Time[i]=k表示給你i分鐘最多能用到k分鐘,如果Time[t]==t表示剛好用完t分鐘,否則最多就是用到Time[t]分鐘,差t-Time[t]分鐘;另外用num[i]=k用來記錄i分鐘能吃k個漢堡。