一天,小紫被賦予了一個運送貨物的任務,雇主給了她一輛不管是造型或是功能都很奇異的大貨車。
這輛貨車會先把車後面的一條長條狀的載物臺放下來,每個等間隔距離的位置都裝有一個載物箱,為了防止箱子亂動,每個箱子都被定死了位置。
雇主告訴小紫,由於他所剩時間不多,希望她到了指定地點後把盡量讓載回來的物品價值最大,這樣生意才至少能夠做的不會太慘,另外就是每個物品都有標示重量和價值,所以不用擔心計算上的問題。
小紫很順利地將貨車開到了指定地點,面對這些排列整齊的貨物,小紫很輕鬆地就想到了著名的資訊問題──背包問題。
「這太簡單了!波路特石教過我!」
小紫很開心地就寫完了背包問題的程式,實際拿去操作之後才發現事情大條了!將載物臺捲上去的馬達居然無法運作,還發出了恐怖的聲音。
認為自己計算沒錯的小紫滿腦子疑惑,思索了一陣子才發現問題的關鍵點──力矩!
重物如果放在離馬達越遠的地方,所造成的力矩就會越大,進而使轉動的困難度大大增加,經過精密的計算後,小紫好不容易才計算出了最大承受上限的力矩,可是卻不知道接下來如何進行下去。
現在告訴你力矩承受上限為τ(重量×長度),每個箱子間隔都是一長度單位,載物臺的長度最多只能放下L個物品,和每個物品的重量和價值,你能夠告訴小紫她能載回去的最大價值嗎?
輸入首行會有三個數字以空格隔開
分別代表物品數量n、力矩承受上限τ、載物臺長度L
接下來n行各有兩個數字wi、vi以空格隔開,代表第i個物品的重量及價值。
1≤L≤n≤200、1≤τ≤1000、1≤wi、vi≤100
輸出在力矩承受上限內載物可得到的最大價值。
5 120 5 20 30 80 60 30 40 30 25 10 20
90
Hint:
以以下順序擺設物品:
20 30 10
(30) (40) (20)
所造成的力矩為20×1+30×2+10×3 = 110
得到的價值為 30+40+20=90
也同時是最大價值的選法
第1~2測資點滿足n≤20
第3測資點滿足對於所有的1≤i,j≤n都有vi=vj
第4~6測資點滿足n=L
第7~10測資點無特別限制
編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」
|